TY - JOUR
T1 - The complexity of coloring games on perfect graphs
AU - Bodlaender, Hans L.
AU - Kratsch, Dieter
PY - 1992/12/14
Y1 - 1992/12/14
N2 - In this paper we consider the following type of game: two players must color the vertices of a given graph G = (V, E), in a prescribed order, in such a way 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. In this paper, we obtain 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.
AB - In this paper we consider the following type of game: two players must color the vertices of a given graph G = (V, E), in a prescribed order, in such a way 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. In this paper, we obtain 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.
UR - http://www.scopus.com/inward/record.url?scp=0026993954&partnerID=8YFLogxK
M3 - Article
AN - SCOPUS:0026993954
SN - 0304-3975
VL - 106
SP - 309
EP - 326
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 2
ER -