The complexity of coloring games on perfect graphs (Q1202928)

This paper addresses the complexity of deciding which of the players has a winning strategy, for the following type of game: two players must color the vertices of a given graph, in a prescribed order, in such a way that no vertex is colored with a color already given to an adjacent vertex. In one variant of this type of game, the first player that is unable to move loses. In the other variant, the first player wins, iff the game ends with the entire graph colored. The paper studies the problem, when the input graphs are restricted, either to interval graphs, split graphs, or bipartite graphs. For interval graphs, it is shown that for certain orderings of the vertices, a `greedy like' strategy gives optimal play for the second game variant; this gives a polynomial time algorithm to decide which player has a winning strategy. The other results in the paper consist of several NP-hardness, coNP-hardness, and PSPACE-completeness results.