A bound for the game chromatic number of graphs (Q1297403): Difference between revisions

The game chromatic number of a graph is the smallest size of a set of collors, where Alice has a winning strategy in the following game. Alternatingly, Alice and Bob select an uncolored vertex and give it a color, different from the colors of its neighbors. Alice wins if the entire graph has been colored; Bob wins if there is a vertex that cannot be colored. The acyclic chromatic number of a graph is the minimum number of colors, needed to color the vertices such that no two adjacent vertices have the same color, and for any pair of colors, the vertices with that color induce a forest. In this paper it is shown that if a graph has acyclic chromatic number \(k\), then it has game chromatic number at most \(k(k+1)\). From this, it follows that a planar graph has game chromatic number at most 30, a result later improved by Zhu with a different technique to 19. Also, bounds are obtained for the game chromatic number for graphs embeddable on a surface of bounded orientable genus, graphs of bounded treewidth, and series parallel graphs.