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 are using 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 complete successfully the coloring of the graph, when the other one tries to prevent him to achieve it.

Vertex coloring game

The vertex coloring game was introduced in 1981 by Brahms^[1] and rediscovered ten years after by Bodlaender.^[2] Its rules are as follows:

1. Alice and Bob are coloring the vertices of a graph G with a set k of colors.
2. Alice and Bob are taking turns, coloring properly a uncolored vertex (in the standard version, Alice begins).
3. If a vertex v is impossible to color properly (for any color, v has a neighbor colored with it), then Bob wins.
4. If the graph is completely colored, then Alice wins.

The game chromatic number of a graph $G$, denoted by $\chi_g(G)$, is the minimum number of colors needed for Alice to win the vertex coloring game on $G$. Trivially, for every graph $G$, we have $\chi(G) \le \chi_g(G) \le \Delta(G) + 1$, where $\chi(G)$ is the chromatic number of $G$ and $\Delta(G)$ its maximum degree.^[3]

Relation with other notions

Acyclic coloring. Every graph $G$ with acyclic chromatic number $k$ has $\chi_g(G) \le k(k+1)$.^[4]

Marking game. For every graph $G$, $\chi_g(G) \le col_g(G)$, where $col_g(G)$ is the game coloring number of $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$ belongs to at most $c$ cycles, then $\chi_g(G) \le 4+c$.^[5]

Graph Classes

For a class ${\mathcal C}$ of graphs, we denote by $\chi_g({\mathcal C})$ the smallest integer $k$ such that every graph $G$ of ${\mathcal C}$ has $\chi_g(G) \le k$. In other words, $\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:

• Forests: $\chi_g({\mathcal F}) = 4$.^[6] Simple criteria are known to determine the game chromatic number of a forest without vertex of degree 3.^[7] It seems difficult to determine the game chromatic number of forests with vertices of degree 3, even for forests with maximum degree 3.
• Cactuses: $\chi_g({\mathcal C}) = 5$.^[8]
• Outerplanar graphs: $6 \le \chi_g({\mathcal O}) \le 7$.^[9]
• Planar graphs: $7 \le \chi_g({\mathcal P}) \le 17$.^[10]
• Planar graphs of given girth: $\chi_g({\mathcal P}_4) \le 13$,^[11] $\chi_g({\mathcal P}_5) \le 8$, $\chi_g({\mathcal P}_6) \le 6$, $\chi_g({\mathcal P}_8) \le 5$.^[12]
• Toroidal grids: $\chi_g({\mathcal TG}) = 5$.^[13]
• Partial k-trees: $\chi_g({\mathcal T}_k) \le 3k+2$.^[14]
• Interval graphs: $2\omega \le \chi_g({\mathcal I}) \le 3\omega-2$, where $\omega$ is for a graph the size of its largest clique.^[15]

Cartesian products. The game chromatic number of the cartesian product $G \square H$ is not bounded by a function of $\chi_g(G)$ and $\chi_g(H)$. In particular, the game chromatic number of any complete bipartite graph $K_{n,n}$ is equal to 3, but there is no upper bound for $\chi_g(K_{n,n} \square K_{m,m})$ for arbitrary $n, m$.^[16]

• $\chi_g(K_2 \square P_1) = 2$,
  $\chi_g(K_2 \square P_k) = 3$ if $k \in \{2, 3\}$,
  and $\chi_g(K_2 \square P_k) = 4$ if $k \ge 4$.^[16]
• For any $k \ge 3$, $\chi_g(K_2 \square C_k) = 4$.^[16]
• For any $k$, $\chi_g(K_2 \square K_k) = k+1$.^[16]
• Trees : $\chi_g(T_1 \square T_2) \le 12$.
• Stars : $\chi_g(S_m \square P_1) = 2$, $\chi_g(S_m \square P_2) = 3$,
  and $\chi_g(S_m \square P_n) = \chi_g(S_m \square C_n) = 4$ if $n \ge 3$.^[17]
• Wheels : $\chi_g(P_2 \square W_n) = 5$ if $n \ge 9$.^[17]
• Complete bipartite graphs : $\chi_g(P_2 \square K_{m,n}) = 5$ if $m, n \ge 5$.^[17]

Open problems

These questions are still open to this date.

More colors for Alice ^[18] 

• Suppose Alice has a winning strategy for the vertex coloring game on a graph G with k colors. Does she have one for k+1 colors ?
  One would expect the answers to be "yes", as having more colors seems an advantage to Alice. However, no proof exists that this statement is true.
• Is there a function f such that, if Alice has a winning strategy for the vertex coloring game on a graph G with k colors, then Alice has a winning strategy on G with f(k) ?
  Relaxation of the previous question.

Relations with other notions ^[18] 

• Suppose a hereditary class of graphs (i.e. a class of graphs closed by subgraphs) has bounded game chromatic number. Is it true that this class of graph has bounded game coloring number ?
• Suppose a hereditary class of graphs (i.e. a class of graphs closed by subgraphs) has bounded game chromatic number. Is it true that this class of graph has bounded arboricity ?
• Is it true that a hereditary class of graphs of bounded game chromatic number has bounded acyclic chromatic number ?

Reducing maximum degree ^[7] 

• Conjecture: Is $F$ is a forest, there exists $F' \subseteq F$ such that $\Delta(F') \le \chi_g(F)$ and $\chi_g(F') = \chi_g(F)$.
• Let ${\mathcal G}$ be the class of graphs such that for any $G \in {\mathcal G}$, there exists $G' \subseteq G$ such that $\Delta(G') \le \chi_g(G)$ and $\chi_g(G') = \chi_g(G)$. What families of graphs are in ${\mathcal G}$ ?

Hypercubes^[16] 

• Is it true that $\chi_g(G) = n+1$ for any hypercube $Q_n$ ?
  It is known to be true true for $n \le 4$.^[16]

Edge coloring game

The edge coloring game, introduced by Lam, Shiu and Zu,^[19] is similar to the vertex coloring game, except Alice and Bob construct a proper edge coloring instead of a proper vertex coloring. Its rules are as follows:

1. Alice and Bob are coloring the edges a graph G with a set k of colors.
2. Alice and Bob are taking turns, coloring properly a uncolored edge (in the standard version, Alice begins).
3. If an edge e is impossible to color properly (for any color, e is adjacent to an edge colored with it), then Bob wins.
4. If the graph is completely edge-colored, then Alice wins.

Although this game can be considered as a particular case of the vertex coloring game on line graphs, it is mainly considered in the scientific literature as a distinct game. The game chromatic index of a graph $G$, denoted by $\chi'_g(G)$, is the minimum number of colors needed for Alice to win this game on $G$.

General case

For every graph G, $\chi'(G) \le \chi'_g(G) \le 2\Delta(G) -1$. There are graphs reaching these bounds but all the graphs we know reaching this upper bound have small maximum degree.^[19] There exists graphs with $\chi'_g(G) > 1.008\Delta(G)$ for arbitrary large values of $\Delta(G)$.^[20]

Conjecture. There is an $\epsilon > 0$ such that, for any arbitrary graph $G$, we have $\chi'_g(G) \le (2-\epsilon)\Delta(G)$.
This conjecture is true when $\Delta(G)$ is large enough compared to the number of vertices in $G$.^[20]

• Arboricity. Let $a(G)$ be the arboricity of a graph $G$. Every graph $G$ with maximum degree $\Delta(G)$ has $\chi'_g(G) \le \Delta(G) + 3a(G) - 1$.^[21]

Graph Classes

For a class ${\mathcal C}$ of graphs, we denote by $\chi'_g({\mathcal C})$ the smallest integer $k$ such that every graph $G$ of ${\mathcal C}$ has $\chi'_g(G) \le k$. In other words, $\chi'_g({\mathcal C})$ is the exact upper bound for the game chromatic index of graphs in this class. This value is known for several standard graph classes, and bounded for some others:

• Wheels: $\chi'_g(W_3) = 5$ and $\chi'_g(W_n) = n+1$ when $n\ge4$.^[19]
• Forests : $\chi'_g({\mathcal F}_\Delta) \le \Delta + 1$ when $\Delta \ne 4$, and $5 \le \chi'_g({\mathcal F}_4) \le 6$.^[22]
  Moreover, if every tree of a forest $F$ of ${\mathcal F}_4$ is obtained by subdivision from a caterpillar tree or contains no two adjacent vertices with degree 4, then $\chi'_g(F) \le 5$.^[23]

Open Problems

Upper bound. Is there a constant $c \ge 2$ such that $\chi'_g(G) \le \Delta(G) + c$ for each graph $G$ ? If it is true, is $c = 2$ enough ?^[19]

Conjecture on large minimum degrees. There are a $\epsilon > 0$ and an integer $d_0$ such that any graph $G$ with $\delta(G) \ge d_0$ satisfies $\chi'_g(G) \ge (1+\epsilon)\delta(G)$. ^[20]

Incidence coloring game

The incidence coloring game is a graph coloring game, introduced by Andres,^[24] and similar to the vertex coloring game, except Alice and Bob construct a proper incidence coloring instead of a proper vertex coloring. Its rules are as follows:

1. Alice and Bob are coloring the incidences of a graph G with a set k of colors.
2. Alice and Bob are taking turns, coloring properly an uncolored incidence (in the standard version, Alice begins).
3. If an incidence i is impossible to color properly (for any color, i is adjacent to an incident colored with it), then Bob wins.
4. If all the incidences are properly colored, then Alice wins.

The incidence game chromatic number of a graph $G$, denoted by $i_g(G)$, is the minimum number of colors needed for Alice to win this game on $G$.

For every graph $G$ with maximum degree $\Delta$, we have $\frac{3\Delta - 1}{2} < i_g(G) < 3\Delta - 1$.^[24]

Relations with other notions

• (a,d)-Decomposition. This is the best upper bound we know for the general case. If the edges of a graph $G$ can be partitionned into two sets, one of them inducing a graph with arboricity $a$, the second inducing a graph with maximum degree $d$, then $i_g(G) \le \left\lfloor \frac{3\Delta(G) - a}{2} \right\rfloor + 8a + 3d - 1$.^[25]
  If moreover $\Delta(G) \ge 5a + 6d$, then $i_g(G) \le \left\lfloor \frac{3\Delta(G) - a}{2} \right\rfloor + 8a + d - 1$.^[25]
• Degeneracy. If $G$ is a k-degenerated graph with maximum degree $\Delta(G)$, then $i_g(G) \le 2\Delta(G) + 4k - 2$. Moreover, $i_g(G) \le 2\Delta(G) + 3k - 1$ when $\Delta(G) \ge 5k - 1$ and $i_g(G) \le \Delta(G) + 8k - 2$ when $\Delta(G) \le 5k -1$.^[24]

Graph Classes

For a class ${\mathcal C}$ of graphs, we denote by $i_g({\mathcal C})$ the smallest integer $k$ such that every graph $G$ of ${\mathcal C}$ has $i_g(G) \le k$.

• Paths : For $k \ge 13$, $i_g(P_k) = 5$.
• Cycles : For $k \ge 3$, $i_g(C_k) = 5$.^[26]
• Stars : For $k \ge 1$, $i_g(S_{2k}) = 3k$.^[24]
• Wheels : For $k \ge 6$, $i_g(W_{2k+1}) = 3k + 2$. For $k \ge 7$, $i_g(W_{2k}) = 3k$.^[24]
• Subgraphs of Wheels : For $k \ge 13$, if $G$ is a subgraph of $W_k$ having $S_k$ as a subgraph, then $i_g(G) = \left\lceil \frac{3k}{2} \right\rceil$.^[27]

Open Problems

• Is the upper bound $i_g(G) < 3\Delta(G) - 1$ tight for every value of $\Delta(G)$ ?^[24]
• Is the incidence game chromatic number a monotonic parameter (i.e. is it as least as big for a graph G as for any subgraph of G) ?^[24]

Notes

1. Gardner (1981)
2. Bodlaender (1991)
3. With less colors than the chromatic number, there is no proper coloring of G and so Alice cannot win. With more colors than the maximum degree, there is always an available color for coloring a vertex and so Alice cannot lose.
4. Dinski & Zhu (1999)
5. Junosza-Szaniawski & Roej (2010)
6. Faigle et al. (1993), and implied by Junosza-Szaniawski & Roej (2010)
7. Dunn et al. (2014)
8. Sidorowicz (2007), and implied by Junosza-Szaniawski & Roej (2010)
9. Guan & Zhu (1999)
10. Upper bound by Zhu (2008), improving previous bounds of 33 in Kierstead & Trotter (1994), 30 implied by Dinski & Zhu (1999), 19 in Zhu (1999) and 18 in Kierstead (2000). Lower bound claimed by Kierstead & Trotter (1994). See a survey dedicated to the game chromatic number of planar graphs in Bartnicki et al. (2007).
11. Sekigushi (2014)
12. He et al. (2002)
13. Raspaud & Wu (2009)
14. Zhu (2000)
15. Faigle et al. (1993)
16. Peterin (2007)
17. Sia (2009)
18. Zhu (1999)
19. Lam, Shiu & Zu (1999)
20. Beveridge et al. (2008)
21. Bartnicki & Grytczuk (2008), improving results on k-degenerated graphs in Cai & Zhu (2001)
22. Upper bound of Δ+2 by Lam, Shiu & Zu (1999), then bound of Δ+1 by Erdös et al. (2004) for cases Δ=3 and Δ≥6, and by Andres (2006) for case Δ=5.
23. Conditions on forests with Δ=4 are in Chan & Nong (2014)
24. Andres (2009a), see also erratum in Andres (2009b)
25. Charpentier & Sopena (2014), extending results of Charpentier & Sopena (2013).
26. Kim (2011), improving a similar result for k ≥ 7 in Andres (2009a) (see also erratum in Andres (2009b))
27. Kim (2011)

References (chronological order)

• Gardner, Martin (1981). "Mathematical Games". Scientific American. Vol. 23.
• Bodlaender, Hans L. (1991). "On the complexity of some coloring games". Lecture Notes in Computer Science 484: 30–40. doi:10.1007/3-540-53832-1_29.
• Faigle, Ulrich; Kern, Walter; Kierstead, Henry A.; Trotter, William T. (1993). "On the Game Chromatic Number of some Classes of Graphs" (PDF). Ars Combinatoria 35 (17): 143–150.
• Kierstead, Henry A.; Trotter, William T. (1994). "Planar Graph Coloring with an Uncooperative Partner" (PDF). Journal of Graph Theory 18 (6): 564–584. doi:10.1002/jgt.3190180605.
• Dinski, Thomas; Zhu, Xuding (1999). "A bound for the game chromatic number of graphs". Discrete Mathematics 196: 109–115. doi:10.1016/s0012-365x(98)00197-6.
• Guan, D. J.; Zhu, Xuding (1999). "Game chromatic number of outerplanar graphs". Journal of Graph Theory 30 (1): 67–70. doi:10.1002/(sici)1097-0118(199901)30:1<67::aid-jgt7>3.0.co;2-m.
• Lam, Peter C. B.; Shiu, Wai C.; Xu, Baogang (1999). "Edge game coloring of graphs" (PDF). Graph Theory Notes N.Y. 37: 17–19.
• Zhu, Xuding (1999). "The Game Coloring Number of Planar Graphs". Journal of Combinatorial Theory, Series B 75 (2): 245–258. doi:10.1006/jctb.1998.1878.
• Kierstead, Henry A. (2000). "A Simple Competitive Graph Coloring Algorithm". Journal of Combinatorial Theory, Series B 78 (1): 57–68. doi:10.1006/jctb.1999.1927.
• Zhu, Xuding (2000). "The game coloring number of pseudo partial k-trees". Discrete Mathematics 215 (1-3): 245–262. doi:10.1016/s0012-365x(99)00237-x.
• Cai, Leizhen; Zhu, Xuding (2001). "Game Chromatic Index of k-Degenerate Graphs". Journal of Graph Theory 36: 144–155. doi:10.1002/1097-0118(200103)36:3<144::aid-jgt1002>3.0.co;2-f.
• He, Wenjie; Hou, Xiaoling; Lih, Ko-Wei; Shao, Jiating; Wang, Weifan; Zhu, Xuding (2002). "Edge-partitions of planar graphs and their game coloring numbers". Journal of Graph Theory 41: 307–311. doi:10.1002/jgt.10069.
• Erdös, Peter L.; Faigle, Ulrich; Hochstättler, Winfried; Kern, Walter (2004). "Note on the game chromatic index of trees". Theoretical Computer Science 313 (3): 371–376. doi:10.1016/j.tcs.2002.10.002.
• Andres, Stephan D. (2006). "The game chromatic index of forests of maximum degree Δ ⩾ 5". Discrete Applied Mathematics 154 (9): 1317–1323. doi:10.1016/j.dam.2005.05.031.
• Bartnicki, Tomasz; Grytczuk, Jaroslaw; Kierstead, H. A.; Zhu, Xuding (2007). "The Map-Coloring Game" (PDF). American Mathematical Monthly 114 (9): 793–803. JSTOR 27642332.
• Peterin, Iztok (2007). "Game chromatic number of Cartesian product graphs". Electronic Notes in Discrete Mathematics 29: 353–357. doi:10.1016/j.endm.2007.07.060.
• Sidorowicz, Elżbieta (2007). "The game chromatic number and the game colouring number of cactuses". Information Processing Letters 102: 147–151. doi:10.1016/j.ipl.2006.12.003.
• Bartnicki, Tomasz; Grytczuk, Jarosław (2008). "A Note on the Game Chromatic Index of Graphs". Graphs and Combinatorics 24 (2): 67–70. doi:10.1007/s00373-008-0774-z.
• Beveridge, Andrew; Bohman, Tom; Friezeb, Alan; Pikhurko, Oleg (2008). "Game chromatic index of graphs with given restrictions on degrees". Theoretical Computer Science 407 (1-3): 242–249. doi:10.1016/j.tcs.2008.05.026.
• Zhu, Xuding (2008). "Refined activation strategy for the marking game". Journal of Combinatorial Theory, Series B 98 (1): 1–18. doi:10.1016/j.jctb.2007.04.004.
• Andres, Stefan D. (2009). "The incidence game chromatic number". Discrete Applied Mathematics 157 (9): 1980–1987. doi:10.1016/j.dam.2007.10.021.
• Andres, Stefan D. (2009). "Erratum to: The incidence game chromatic number". Discrete Applied Mathematics 158 (6): 728. doi:10.1016/j.dam.2009.11.017.
• Raspaud, André; Jiaojiao, Wu (2009). "Game chromatic number of toroidal grids". Information Processing Letters 109 (21-22): 1183–1186. doi:10.1016/j.ipl.2009.08.001.
• Sia, Charmaine (2009). "The Game Chromatic Number of Some Families of Cartesian Product Graphs" (PDF). AKCE International Journal of Graphs and Combinatorics 6 (2): 315–327.
• Junosza-Szaniawski, Konstanty; Roej, Łukasz (2010). "Game chromatic number of graphs with locally bounded number of cycles". Information Processing Letters 110 (17): 757–760. doi:10.1016/j.ipl.2010.06.004.
• Kim, John Y. (2011). "The incidence game chromatic number of paths and subgraphs of wheels". Discrete Applied Mathematics 159 (8): 683–694. doi:10.1016/j.dam.2010.01.001.
• Charpentier, Clément; Sopena, Éric (2013). "Incidence coloring game and arboricity of graphs". Lecture Notes in Computer Science 8288: 106–114. doi:10.1007/978-3-642-45278-9_10.
• Chan, Wai H.; Nong, Ge (2014). "The game chromatic index of some trees of maximum degree 4". Discrete Applied Mathematics 170: 1–6. doi:10.1016/j.dam.2014.01.003.
• Sekigushi, Yosuke (2014). "The game coloring number of planar graphs with a given girth". Discrete Mathematics 300: 11–16. doi:10.1016/j.disc.2014.04.011.
• Charpentier, Clément; Sopena, Éric (2014). "The incidence game chromatic number of (a,d)-decomposable graphs". Journal of Discrete Algorithms. doi:10.1016/j.jda.2014.10.001.
• Dunn, Charles; Larsen, Victor; Lindke, Kira; Retter, Troy; Toci, Dustin (2014). "The game chromatic number of trees and forests". arXiv:1410.5223 [math.CO].