On the Game Chromatic Number of some Classes of Graphs

Abstract

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)\le 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.