@misc{Lukac2004, author = {Lukac, Sascha}, title = {Holes, Antiholes and Maximal Cliques in a Railway Model for a Single Track}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7939}, number = {04-18}, year = {2004}, abstract = {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\$.}, language = {en} }