Game-perfect Digraphs — Paths and Cycles
Stephan Dominique Andres · 2009
We consider an extension of Bodlaender’s graph coloring game [5] which is played on digraphs instead of undirected graphs and in which the first player is allowed to miss a turn. This game defines the A-game chromatic number of a digraph. A digraph D is called A-perfect if for every induced subdigraph H of D, the A-game chromatic number of H is equal to the size of the largest clique in H. We characterize all A-perfect semiorientations of complete graphs with clique number 2, and all A-perfect paths and cycles.