Graph coloring game

The graph coloring game is a mathematical game related to graph theory. Coloring game problems arose as game-theoretic versions of well-known graph coloring problems. In a coloring game, two players use a given set of colors to construct a coloring of a graph, following specific rules depending on the game we consider. One player tries to successfully complete the coloring of the graph, while the other one tries to prevent him from achieving it.

Vertex coloring game The vertex coloring game was introduced in 1981 by Steven Brams as a map-coloring game and rediscovered ten years after by Bodlaender. Its rules are as follows:

Alice and Bob color the vertices of a graph G with a set k of colors. Alice and Bob take turns, coloring properly an uncolored vertex (in the standard version, Alice begins). If a vertex v is impossible to color properly (for any color, v has a neighbor colored with it), then Bob wins. If the graph is completely colored, then Alice wins. The game chromatic number of a graph G {\displaystyle G} , denoted by χ g ( G ) {\displaystyle \chi _{g}(G)} , is the minimum number of colors needed for Alice to win the vertex coloring game on G {\displaystyle G} . Trivially, for every graph G {\displaystyle G} , we have χ ( G ) ≤ χ g ( G ) ≤ Δ ( G ) + 1 {\displaystyle \chi (G)\leq \chi _{g}(G)\leq \Delta (G)+1} , where χ ( G ) {\displaystyle \chi (G)} is the chromatic number of G {\displaystyle G} and Δ ( G ) {\displaystyle \Delta (G)} its maximum degree. In the 1991 Bodlaender's paper, the computational complexity was left as "an interesting open problem". Only in 2020 it was proved that the game is PSPACE-Complete.

Relation with other notions Acyclic coloring. Every graph G {\displaystyle G} with acyclic chromatic number k {\displaystyle k} has χ g ( G ) ≤ k ( k + 1 ) {\displaystyle \chi _{g}(G)\leq k(k+1)} . Marking game. For every graph G {\displaystyle G} , χ g ( G ) ≤ c o l g ( G ) {\displaystyle \chi _{g}(G)\leq col_{g}(G)} , where c o l g ( G ) {\displaystyle col_{g}(G)} is the game coloring number of G {\displaystyle G} . Almost every known upper bound for the game chromatic number of graphs are obtained from bounds on the game coloring number. Cycle-restrictions on edges. If every edge of a graph G {\displaystyle G} belongs to at most c {\displaystyle c} cycles, then χ g ( G ) ≤ 4 + c {\displaystyle \chi _{g}(G)\leq 4+c} .

Graph Classes For a class C {\displaystyle {\mathcal {C}}} of graphs, we denote by χ g ( C ) {\displaystyle \chi _{g}({\mathcal {C}})} the smallest integer k {\displaystyle k} such that every graph G {\displaystyle G} of C {\displaystyle {\mathcal {C}}} has χ g ( G ) ≤ k {\displaystyle \chi _{g}(G)\leq k} . In other words, χ g ( C ) {\displaystyle \chi _{g}({\mathcal {C}})} is the exact upper bound for the game chromatic number of graphs in this class. This value is known for several standard graph classes, and bounded for some others:

… excerpt ends here. Continue reading the full article.