The game coloring number of planar graphs (Q1305532): Difference between revisions

The game chromatic number of a graph \(G=(V, E)\) is the minimum number of colors, such that Alice has a winning strategy in the following game: turnwise, Alice and Bob color an uncolored vertex \(v\) of \(V\) with a color, different from colors already assigned to the neighbors of \(v\). Alice wins when \(G\) is colored; Bob wins when there are vertices to which no color can be assigned. In the coloring game, Alice and Bob turnwise color a vertex of \(G\). The outcome of the game is \(1+k\), where \(k\) is the maximum number of colored neighbors of a vertex when it is colored. Alice tries to minimize the outcome, while Bob tries to maximize it. The minimum outcome when Alice plays perfectly is the game coloring number, which is an upper bound for the game chromatic number. In this paper, it is shown that the game coloring number (and hence also the game chromatic number) of a planar graph is at most 19, improving upon an earlier bound of 30. This bound is obtained using the notion of light edges, a decomposition of the planar graph into subgraphs with special properties, and a detailed strategy for Alice. The paper also poses a number of central open questions in this area of research.