Game-perfect graphs

Andres, Dominique (2007) Game-perfect graphs.
Published in: Mathematical Methods of Operations Research Vol. 69 (2). pp. 235-250.


A graph coloring game introduced by Bodlaender [3] as coloring construction game is the following. Two players, Alice and Bob, alternately color vertices of a given graph G with a color from a given color set C, so that adjacent vertices receive distinct colors. Alice has the first move. The game ends if no move is possible any more. Alice wins if every vertex of G is colored at the end, otherwise Bob wins. We consider two variants of Bodlaender's graph coloring game: one (A) in which Alice has the right to have the first move and to miss a turn, the other (B) in which Bob has these rights. These games define the A-game chromatic number resp. the B-game chromatic number of a graph. For such a variant g, a graph is g-perfect if, for every induced subgraph H of G, the clique number of H equals the g-game chromatic number of H. We determine those graphs for which the game chromatic numbers are 2 and prove that the triangle-free B-perfect graphs are exactly the forests of stars, and the triangle-free A-perfect graphs are exactly the graphs each component of which is a complete bipartite graph or a complete bipartite graph minus one edge or a singleton. From these results we may easily derive the set of triangle-free game-perfect graphs with respect to Bodlaender's original game. We also determine the B-perfect graphs with clique number 3. As a general result we prove that complements of bipartite graphs are A-perfect.

Download: [img] Postscript - Preprinted Version
Download (397kB) | Preview
Download: [img] PDF - Preprinted Version
Download (190kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2007-564
Depositing User: Dominique Andres
Date Deposited: 04 Dec 2007 00:00
Last Modified: 19 Dec 2011 09:44