TY - GEN A1 - Lukac, Sascha T1 - Holes, Antiholes and Maximal Cliques in a Railway Model for a Single Track N2 - We present a graph theoretical model for scheduling trains on a single unidirectional track between two stations. The set of departures of all possible train types at all possible (discrete) points of time is turned into an undirected graph $\Gneu$ by joining two nodes if the corresponding departures are in conflict. This graph $\Gneu$ has no odd antiholes and no $k$-holes for any integer $k\geq 5$. In particular, any finite, node induced subgraph of $\Gneu$ is perfect. For any integer $r\geq 2$ we construct minimal headways for $r$ train types so that the resulting graph $\Gneu$ has $2r$-antiholes and $4$-holes at the same time. Hence, $\Gneu$ is neither a chordal graph nor the complement of a chordal graph, in general. At the end we analyse the maximal cliques in $G$. T3 - ZIB-Report - 04-18 KW - perfect graphs KW - holes KW - anti holes KW - cliques KW - railway Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7939 ER -