# Game-perfect graphs

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

## Abstract

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.

Actions:
Download: Postscript - Preprinted Version Download (388Kb) | Preview PDF - Preprinted Version Download (185Kb) | Preview HTML CitationASCII CitationOpenURL ContextObjectEndNoteBibTeXMPEG-21 DIDLEP3 XMLJSONAtomReference ManagerSimple MetadataRefer View Item (Login required)
Content information:
Item Type: Article 5 (Google Scholar) | game-perfect game chromatic number perfect graphs A-perfect B-perfect bipartite graphs 05-XX Combinatorics > 05Cxx Graph theory > 05C17 Perfect graphs 91-XX Game theory, economic, social and behavioral sciences > 91Axx Game theory > 91A43 Games involving graphs 05-XX Combinatorics > 05Cxx Graph theory > 05C15 Coloring of graphs and hypergraphs Institute of Computer Science > Computer Science Department - Prof. Dr. SchraderMathematical Institute > Prof. Dr. Faigle
Deposit Information:
ZAIK Number: zaik2007-564 Dominique Andres 04 Dec 2007 00:00 19 Dec 2011 09:44 http://e-archive.informatik.uni-koeln.de/id/eprint/564