Graph coloring game explained
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.
Vertex coloring game
The vertex coloring game was introduced in 1981 by Brams 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
, denoted by
, is the minimum number of colors needed for Alice to win the vertex coloring game on
. Trivially, for every graph
, we have
\chi(G)\le\chig(G)\le\Delta(G)+1
, where
is the chromatic number of
and
its maximum
degree.
[1] 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
with
acyclic chromatic number
has
.
Marking game. For every graph
,
, where
is the game coloring number of
. 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
belongs to at most
cycles, then
.
Graph Classes
For a class
of graphs, we denote by
the smallest integer
such that every graph
of
has
. In other words,
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:
.
[2] Simple criteria are known to determine the game chromatic number of a forest without vertex of degree 3. It seems difficult to determine the game chromatic number of forests with vertices of degree 3, even for forests with maximum degree 3.
.
[3]
.
.
[4]
,
,
,
.
.
.
2\omega\le\chig({lI})\le3\omega-2
, where
is for a graph the size of its largest
clique.
Cartesian products.The game chromatic number of the cartesian product
is not bounded by a function of
and
. In particular, the game chromatic number of any complete bipartite graph
is equal to 3, but there is no upper bound for
for arbitrary
. On the other hand, the game chromatic number of
is bounded above by a function of
and
. In particular, if
and
are both at most
, then
\chig(G\squareH)\let5-t3+t2
.
- For a single edge we have:
\begin{align}
\chig(K2\squarePk)&=\begin{cases}2&k=1\ 3&k=2,3\ 4&k\ge4\end{cases}\\
\chig(K2\squareCk)&=4&&k\ge3\\
\chig(K2\squareKk)&=k+1\end{align}
\begin{align}
\chig(Sm\squarePk)&=\begin{cases}2&k=1\ 3&k=2\ 4&k\ge3\end{cases}\\
\chig(Sm\squareCk)&=4&&k\ge3\end{align}
if
if
Open problems
These questions are still open to this date.
Edge coloring game
The edge coloring game, introduced by Lam, Shiu and Zu, 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:
- Alice and Bob are coloring the edges a graph G with a set k of colors.
- Alice and Bob are taking turns, coloring properly an uncolored edge (in the standard version, Alice begins).
- If an edge e is impossible to color properly (for any color, e is adjacent to an edge colored with it), then Bob wins.
- 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
, denoted by
, is the minimum number of colors needed for Alice to win this game on
.
General case
For every graph G,
\chi'(G)\le\chi'g(G)\le2\Delta(G)-1
. There are graphs reaching these bounds but all the graphs we know reaching this upper bound have small maximum degree. There exists graphs with
for arbitrary large values of
.
Conjecture. There is an
such that, for any arbitrary graph
, we have
\chi'g(G)\le(2-\epsilon)\Delta(G)
.
This conjecture is true when
is large enough compared to the number of vertices in
.
be the
arboricity of a graph
. Every graph
with maximum
degree
has
\chi'g(G)\le\Delta(G)+3a(G)-1
.
[5] Graph Classes
For a class
of graphs, we denote by
the smallest integer
such that every graph
of
has
. In other words,
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:
and
when
.
\chi'g({lF}\Delta)\le\Delta+1
when
, and
.
[6] Moreover, if every tree of a forest
of
is obtained by subdivision from a
caterpillar tree or contains no two adjacent vertices with degree 4, then
.
[7] Open Problems
Upper bound. Is there a constant
such that
for each graph
? If it is true, is
enough ?
Conjecture on large minimum degrees. There are a
and an integer
such that any graph
with
satisfies
\chi'g(G)\ge(1+\epsilon)\delta(G)
.
Incidence coloring game
The incidence coloring game is a graph coloring game, introduced by Andres,[8] 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:
- Alice and Bob are coloring the incidences of a graph G with a set k of colors.
- Alice and Bob are taking turns, coloring properly an uncolored incidence (in the standard version, Alice begins).
- If an incidence i is impossible to color properly (for any color, i is adjacent to an incident colored with it), then Bob wins.
- If all the incidences are properly colored, then Alice wins.
The incidence game chromatic number of a graph
, denoted by
, is the minimum number of colors needed for Alice to win this game on
.
For every graph
with maximum degree
, we have
.
[8] 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
can be partitioned into two sets, one of them inducing a graph with
arboricity
, the second inducing a graph with maximum degree
, then
ig(G)\le\left\lfloor
\right\rfloor+8a+3d-1
.
[9] If moreover
, then
ig(G)\le\left\lfloor
\right\rfloor+8a+d-1
.
is a
k-degenerated graph with maximum
degree
, then
. Moreover,
when
and
when
.
[8] Graph Classes
For a class
of graphs, we denote by
the smallest integer
such that every graph
of
has
.
,
.
,
.
[10]
,
.
[8]
,
. For
,
.
[8]
, if
is a subgraph of
having
as a subgraph, then
ig(G)=\left\lceil
\right\rceil
.
Open Problems
tight for every value of
?
[8] - 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) ?[8]
References (chronological order)
- Gardner. Martin. 1981. Mathematical Games. Scientific American. 23.
- Book: Bodlaender
, Hans L.
. Lecture Notes in Computer Science. Graph-Theoretic Concepts in Computer Science. 1991. On the complexity of some coloring games. 484. 30–40. 10.1007/3-540-53832-1_29. 978-3-540-53832-5. 10.1.1.18.9992.
- Faigle . Ulrich . Kern . Walter . Kierstead . Henry A. . Trotter . William T. . William T. Trotter . 1993 . On the Game Chromatic Number of some Classes of Graphs . Ars Combinatoria . 35 . 17 . 143–150 . .
- Kierstead . Henry A. . Trotter . William T. . 1994 . Planar Graph Coloring with an Uncooperative Partner . Journal of Graph Theory . 18 . 6 . 564–584 . 10.1002/jgt.3190180605.
- Dinski. Thomas. Zhu. Xuding. 1999. A bound for the game chromatic number of graphs. Discrete Mathematics. 196. 1–3. 109–115. 10.1016/s0012-365x(98)00197-6. free.
- Guan. D. J.. Zhu. Xuding. 1999. Game chromatic number of outerplanar graphs. Journal of Graph Theory. 30. 1. 67–70. 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 . 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. 10.1006/jctb.1998.1878. free.
- Kierstead. Henry A.. 2000. A Simple Competitive Graph Coloring Algorithm. Journal of Combinatorial Theory, Series B. 78. 1. 57–68. 10.1006/jctb.1999.1927. free.
- Zhu. Xuding. 2000. The game coloring number of pseudo partial k-trees. Discrete Mathematics. 215. 1–3. 245–262. 10.1016/s0012-365x(99)00237-x.
- Cai. Leizhen. Zhu. Xuding. 2001. Game Chromatic Index of k-Degenerate Graphs. Journal of Graph Theory. 36. 3. 144–155. 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. 4. 307–311. . 10.1002/jgt.10069. 20929383. free.
- 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. . 10.1016/j.tcs.2002.10.002. free.
- Andres. Stephan D. . 2006. The game chromatic index of forests of maximum degree Δ ⩾ 5. Discrete Applied Mathematics. 154. 9. 1317–1323. 10.1016/j.dam.2005.05.031.
- Bartnicki . Tomasz . Grytczuk . Jaroslaw . Kierstead . H. A. . Zhu . Xuding . 2007 . The Map-Coloring Game . American Mathematical Monthly . 114 . 9 . 793–803 . 27642332 . . 10.1080/00029890.2007.11920471. 15901267 .
- Peterin. Iztok. 2007. Game chromatic number of Cartesian product graphs. Electronic Notes in Discrete Mathematics. 29. 353–357. 10.1016/j.endm.2007.07.060. 10.1.1.107.111.
- Sidorowicz . Elżbieta . 2007 . The game chromatic number and the game colouring number of cactuses . Information Processing Letters . 102 . 4 . 147–151 . 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. 10.1007/s00373-008-0774-z. 19373685.
- 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. 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. 10.1016/j.jctb.2007.04.004. free.
- Andres. Stefan D. . 2009. The incidence game chromatic number. Discrete Applied Mathematics. 157. 9. 1980–1987. . 10.1016/j.dam.2007.10.021. free.
- Andres. Stefan D. . 2009. Erratum to: The incidence game chromatic number. Discrete Applied Mathematics. 158. 6. 728. . 10.1016/j.dam.2009.11.017. free.
- Raspaud. André. Jiaojiao. Wu. 2009. Game chromatic number of toroidal grids. Information Processing Letters. 109. 21–22. 1183–1186. 10.1016/j.ipl.2009.08.001.
- Sia . Charmaine . 2009 . The Game Chromatic Number of Some Families of Cartesian Product Graphs . https://wayback.archive-it.org/all/20111114043919/http://www.math.harvard.edu/~sia/papers/game_chromatic_number_cartesian.pdf . dead . 2011-11-14 . AKCE International Journal of Graphs and Combinatorics . 6 . 2 . 315–327 . 2014-07-16.
- Junosza-Szaniawski . Konstanty . Rożej . Łukasz . 2010 . Game chromatic number of graphs with locally bounded number of cycles . Information Processing Letters . 110 . 17 . 757–760 . 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. 10.1016/j.dam.2010.01.001. free.
- Book: Charpentier. Clément. Sopena. Éric. Combinatorial Algorithms. Incidence Coloring Game and Arboricity of Graphs. Lecture Notes in Computer Science. 2013. 8288. 106–114. 10.1007/978-3-642-45278-9_10. 1304.0166. 978-3-642-45277-2. 14707501.
- Chan. Wai H.. Nong. Ge . 2014. The game chromatic index of some trees of maximum degree 4. Discrete Applied Mathematics. 170. 1–6. 10.1016/j.dam.2014.01.003. free.
- Sekigushi. Yosuke. 2014. The game coloring number of planar graphs with a given girth. Discrete Mathematics. 300. 11–16. 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. 10.1016/j.jda.2014.10.001. 31. 14–25. 1102795.
- Dunn. Charles. Larsen. Victor. Lindke. Kira. Retter. Troy. Toci. Dustin. 2014. The game chromatic number of trees and forests. 1410.5223. math.CO. .
- Costa . Eurinardo . Pessoa . Victor Lage . Soares . Ronan . Sampaio . Rudini . 2020 . PSPACE-completeness of two graph coloring games . Theoretical Computer Science . 824-825 . 36–45 . 10.1016/j.tcs.2020.03.022 . 218777459 . .
- Bradshaw. Peter. 2021. Graph colorings with restricted bicolored subgraphs: II. The graph coloring game. Journal of Graph Theory. 100. 2. 371–383. 10.1002/jgt.22786. 2008.13275. 221377336.
Notes and References
- 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.
- , and implied by
- , and implied by
- Upper bound by, improving previous bounds of 33 in, 30 implied by, 19 in and 18 in . Lower bound claimed by . See a survey dedicated to the game chromatic number of planar graphs in .
- , improving results on k-degenerate graphs in
- Upper bound of Δ+2 by, then bound of Δ+1 by for cases Δ=3 and Δ≥6, and by for case Δ=5.
- Conditions on forests with Δ=4 are in
- , see also erratum in
- , extending results of .
- , improving a similar result for k ≥ 7 in (see also erratum in)