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, when the other one tries to prevent him from achieving it. 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, when the other one tries to prevent him from achieving it. The vertex coloring game was introduced in 1981 by Brams and rediscovered ten years after by Bodlaender. Its rules are as follows: 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. 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} . 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: Cartesian products.The game chromatic number of the cartesian product G ◻ H {displaystyle Gsquare H} is not bounded by a function of χ g ( G ) {displaystyle chi _{g}(G)} and χ g ( H ) {displaystyle chi _{g}(H)} . In particular, the game chromatic number of any complete bipartite graph K n , n {displaystyle K_{n,n}} is equal to 3, but there is no upper bound for χ g ( K n , n ◻ K m , m ) {displaystyle chi _{g}(K_{n,n}square K_{m,m})} for arbitrary n , m {displaystyle n,m} .