On the Game Chromatic Number of some Classes of Graphs

Consider the following two-person game on the graph \(G\). Player I and II move alternatingly. Each move consists in coloring a yet uncolored vertex of \(G\) properly using a prespecified set of colors. The game ends when some player can no longer move. Player I wins if all of \(G\) is colored. Otherwise Player II wins. What is the minimal number \(\gamma(G)\) of colors such that Player I has a winning strategy? Improving a result of Bodlaender [1990] we show \(\gamma(T) \leq 4\) for each tree \(T\). We, furthermore, prove \(\gamma(G) = O(\log |G|)\) for graphs \(G\) that are unions of \(k\) trees. Thus, in particular, \(\gamma(G) = O(\log |G|)\) for the class of planar graphs. Finally we bound \(4(G)\) by \(3w(G) – 2\) for interval graphs \(G\). The order of magnitude of \(\gamma(G)\) can generally not be improved for \(k\)-fold trees. The problem remains open for planar graphs.