Complexity of Coloring Games on Perfect Graphs

摘要

Consideration is given to the following type of game: two players must color thevertices of a given graph G (V,E), in a predescribed order, such that no two adjacent vertices are colored with the same color. In one variant, the first player which is unable to move loses the game. In another variant, player 1 wins the game, if and only if the game ends with all vertices colored. Several results on the complexity of the problem to decide whether there is a winning strategy for player 1 in a given game instance, when G is restricted to split graphs, interval graphs, or bipartite graphs is obtained.