Graph coloring game

{{Short description|Class of mathematical games}} [[File:Graph coloring game.gif|thumb|300px|The '''vertex coloring game''' on a given graph between Alice and Bob. Here, vertices labeled "A" are colored by Alice, and "B" by Bob. The players take turns (starting with Alice) coloring properly vertices of the graph. If the graph is fully colored properly at the end, Alice wins. If at any point there is a vertex that becomes impossible to properly color, Bob wins. <br /><br /> The '''game chromatic number''' <math>\chi_g(G)</math> is the minimum number of colors needed for Alice to win the vertex coloring game on <math>G</math>. For this graph, <math>\chi_g(G)=3</math>, as it is the Cartesian product <math>S_5 \square P_2</math><ref name=sia2009>{{harvtxt|Sia|2009}}</ref>]] {{unsolved|mathematics|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?}}

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<ref>{{harvtxt|Gardner|1981}}</ref><ref>{{harvtxt|Bartnicki et al.|2007}}</ref> and rediscovered ten years after by Bodlaender.<ref>{{harvtxt|Bodlaender|1991}}</ref> 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 <math>G</math>, denoted by <math>\chi_g(G)</math>, is the minimum number of colors needed for Alice to win the vertex coloring game on <math>G</math>. Trivially, for every graph <math>G</math>, we have <math>\chi(G) \le \chi_g(G) \le \Delta(G) + 1</math>, where <math>\chi(G)</math> is the chromatic number of <math>G</math> and <math>\Delta(G)</math> its maximum degree.<ref>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.</ref>

In the 1991 Bodlaender's paper,<ref>{{harvtxt|Bodlaender|1991}}</ref> the computational complexity was left as "''an interesting open problem''". Only in 2020 it was proved that the game is PSPACE-Complete.<ref>{{harvtxt|Costa, Pessoa, Soares, Sampaio|2020}}</ref>

===Relation with other notions===

'''Acyclic coloring.''' Every graph <math>G</math> with acyclic chromatic number <math>k</math> has <math>\chi_g(G) \le k(k+1)</math>.<ref>{{harvtxt|Dinski|Zhu|1999}}</ref>

'''Marking game.''' For every graph <math>G</math>, <math>\chi_g(G) \le col_g(G)</math>, where <math>col_g(G)</math> is the game coloring number of <math>G</math>. 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 <math>G</math> belongs to at most <math>c</math> cycles, then <math>\chi_g(G) \le 4+c</math>.<ref>{{harvtxt|Junosza-Szaniawski|Rożej|2010}}</ref>

===Graph Classes===

For a class <math>{\mathcal C}</math> of graphs, we denote by <math>\chi_g({\mathcal C})</math> the smallest integer <math>k</math> such that every graph <math>G</math> of <math>{\mathcal C}</math> has <math>\chi_g(G) \le k</math>. In other words, <math>\chi_g({\mathcal C})</math> 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: <math>\chi_g({\mathcal F}) = 4</math>.<ref>{{harvtxt|Faigle et al.|1993}}, and implied by {{harvtxt|Junosza-Szaniawski|Rożej|2010}}</ref> Simple criteria are known to determine the game chromatic number of a forest without vertex of degree 3.<ref name=dunn2014>{{harvtxt|Dunn et al.|2014}}</ref> It seems difficult to determine the game chromatic number of forests with vertices of degree 3, even for forests with maximum degree 3. * Cactuses: <math>\chi_g({\mathcal C}) = 5</math>.<ref>{{harvtxt|Sidorowicz|2007}}, and implied by {{harvtxt|Junosza-Szaniawski|Rożej|2010}}</ref> * Outerplanar graphs: <math>6 \le \chi_g({\mathcal O}) \le 7</math>.<ref>{{harvtxt|Guan|Zhu|1999}}</ref> * Planar graphs: <math>7 \le \chi_g({\mathcal P}) \le 17</math>.<ref>Upper bound by {{harvtxt|Zhu|2008}}, improving previous bounds of 33 in {{harvtxt|Kierstead|Trotter|1994}}, 30 implied by {{harvtxt|Dinski|Zhu|1999}}, 19 in {{harvtxt|Zhu|1999}} and 18 in {{harvtxt|Kierstead|2000}}. Lower bound claimed by {{harvtxt|Kierstead|Trotter|1994}}. See a survey dedicated to the game chromatic number of planar graphs in {{harvtxt|Bartnicki et al.|2007}}.</ref> * Planar graphs of given girth: <math>\chi_g({\mathcal P}_4) \le 13</math>,<ref>{{harvtxt|Sekigushi|2014}}</ref> <math>\chi_g({\mathcal P}_5) \le 8</math>, <math>\chi_g({\mathcal P}_6) \le 6</math>, <math>\chi_g({\mathcal P}_8) \le 5</math>.<ref>{{harvtxt|He et al.|2002}}</ref> * Toroidal grids: <math>\chi_g({\mathcal TG}) = 5</math>.<ref>{{harvtxt|Raspaud|Wu|2009}}</ref> * Partial ''k''-trees: <math>\chi_g({\mathcal T}_k) \le 3k+2</math>.<ref>{{harvtxt|Zhu|2000}}</ref> * Interval graphs: <math>2\omega \le \chi_g({\mathcal I}) \le 3\omega-2</math>, where <math>\omega</math> is for a graph the size of its largest clique.<ref>{{harvtxt|Faigle et al.|1993}}</ref>

'''Cartesian products.''' The game chromatic number of the cartesian product <math>G \square H</math> is not bounded by a function of <math>\chi_g(G)</math> and <math>\chi_g(H)</math>. In particular, the game chromatic number of any complete bipartite graph <math>K_{n,n}</math> is equal to 3, but there is no upper bound for <math>\chi_g(K_{n,n} \square K_{m,m})</math> for arbitrary <math>n, m</math>.<ref name=peterin2007>{{harvtxt|Peterin|2007}}</ref> On the other hand, the game chromatic number of <math>G \square H</math> is bounded above by a function of <math>\textrm{col}_g(G)</math> and <math>\textrm{col}_g(H)</math>. In particular, if <math>\textrm{col}_g(G)</math> and <math>\textrm{col}_g(H)</math> are both at most <math>t</math>, then <math>\chi_g(G \square H) \le t^5 - t^3 + t^2</math>.<ref name=bradshaw2021>{{harvtxt|Bradshaw|2021}}</ref>

* For a single edge we have:<ref name=peterin2007 /> ::<math>\begin{align} \chi_g(K_2 \square P_k) &= \begin{cases} 2 & k = 1 \\ 3 & k=2,3 \\ 4 & k \ge 4 \end{cases} \\ \chi_g(K_2 \square C_k) &= 4 && k \ge 3 \\ \chi_g(K_2 \square K_k) &= k+1 \end{align}</math> * For stars we have:<ref name=sia2009 /> ::<math>\begin{align} \chi_g(S_m \square P_k) &= \begin{cases} 2 & k = 1 \\ 3 & k=2 \\ 4 & k \ge 3 \end{cases} \\ \chi_g(S_m \square C_k) &= 4 && k \ge 3 \end{align}</math> * Trees: <math>\chi_g(T_1 \square T_2) \le 12.</math> * Wheels: <math>\chi_g(P_2 \square W_n) = 5</math> if <math>n \ge 9.</math><ref name=sia2009 /> * Complete bipartite graphs: <math>\chi_g(P_2 \square K_{m,n}) = 5</math> if <math>m, n \ge 5.</math><ref name=sia2009 />

===Open problems=== These questions are still open to this date.

====More colors for Alice==== * 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 ? <br /> ''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.''<ref name=zhu1999>{{harvtxt|Zhu|1999}}</ref> *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)'' ? <br />''Relaxation of the previous question.'' ====Relations with other notions==== * Suppose a monotone 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'' ? <ref name=zhu1999/> * Suppose a monotone 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 monotone class of graphs of bounded ''game chromatic number'' has bounded ''acyclic chromatic number'' ? ====Reducing maximum degree==== * '''Conjecture:''' Is <math>F</math> is a forest, there exists <math>F' \subseteq F</math> such that <math>\Delta(F') \le \chi_g(F)</math> and <math>\chi_g(F') = \chi_g(F)</math>. <ref name=dunn2014 /> * Let <math>{\mathcal G}</math> be the class of graphs such that for any <math>G \in {\mathcal G}</math>, there exists <math>G' \subseteq G</math> such that <math>\Delta(G') \le \chi_g(G)</math> and <math>\chi_g(G') = \chi_g(G)</math>. What families of graphs are in <math>{\mathcal G}</math> ? ====Hypercubes==== * Is it true that <math>\chi_g(G) = n+1</math> for any hypercube <math>Q_n</math> ? <br />''It is known to be true for <math>n \le 4</math>.''<ref name=peterin2007/>

== Edge coloring game ==

The '''edge coloring game''', introduced by Lam, Shiu and Zu,<ref name=lsz1999>{{harvtxt|Lam|Shiu|Xu|1999}}</ref> 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 <math>G</math>, denoted by <math>\chi'_g(G)</math>, is the minimum number of colors needed for Alice to win this game on <math>G</math>.

===General case===

For every graph ''G'', <math>\chi'(G) \le \chi'_g(G) \le 2\Delta(G) -1</math>. There are graphs reaching these bounds but all the graphs we know reaching this upper bound have small maximum degree.<ref name=lsz1999 /> There exists graphs with <math>\chi'_g(G) > 1.008\Delta(G)</math> for arbitrary large values of <math>\Delta(G)</math>.<ref name=bevetal2008>{{harvtxt|Beveridge|Bohman|Friezeb|Pikhurko|2008}}</ref>

'''Conjecture.''' ''There is an <math>\epsilon > 0</math> such that, for any arbitrary graph <math>G</math>, we have <math>\chi'_g(G) \le (2-\epsilon)\Delta(G)</math>.''<br /> This conjecture is true when <math>\Delta(G)</math> is large enough compared to the number of vertices in <math>G</math>.<ref name=bevetal2008 />

* '''Arboricity.''' Let <math>a(G)</math> be the arboricity of a graph <math>G</math>. Every graph <math>G</math> with maximum degree <math>\Delta(G)</math> has <math>\chi'_g(G) \le \Delta(G) + 3a(G) - 1</math>.<ref>{{harvtxt|Bartnicki|Grytczuk|2008}}, improving results on ''k''-degenerate graphs in {{harvtxt|Cai|Zhu|2001}}</ref>

===Graph Classes===

For a class <math>{\mathcal C}</math> of graphs, we denote by <math>\chi'_g({\mathcal C})</math> the smallest integer <math>k</math> such that every graph <math>G</math> of <math>{\mathcal C}</math> has <math>\chi'_g(G) \le k</math>. In other words, <math>\chi'_g({\mathcal C})</math> 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: <math>\chi'_g(W_3) = 5</math> and <math>\chi'_g(W_n) = n+1</math> when <math>n\ge4</math>.<ref name=lsz1999 /> * Forests : <math>\chi'_g({\mathcal F}_\Delta) \le \Delta + 1 </math> when <math>\Delta \ne 4</math>, and <math>5 \le \chi'_g({\mathcal F}_4) \le 6</math>.<ref>Upper bound of Δ+2 by {{harvtxt|Lam|Shiu|Xu|1999}}, then bound of Δ+1 by {{harvtxt|Erdös et al.|2004}} for cases Δ=3 and Δ≥6, and by {{harvtxt|Andres|2006}} for case Δ=5.</ref> <br /> Moreover, if every tree of a forest <math>F</math> of <math>{\mathcal F}_4</math> is obtained by subdivision from a caterpillar tree or contains no two adjacent vertices with degree 4, then <math>\chi'_g(F) \le 5</math>.<ref>Conditions on forests with Δ=4 are in {{harvtxt|Chan|Nong|2014}}</ref>

=== Open Problems ===

'''Upper bound.''' Is there a constant <math>c \ge 2</math> such that <math>\chi'_g(G) \le \Delta(G) + c</math> for each graph <math>G</math> ? If it is true, is <math>c = 2</math> enough ?<ref name=lsz1999 />

'''Conjecture on large minimum degrees.''' ''There are a <math>\epsilon > 0</math> and an integer <math>d_0</math> such that any graph <math>G</math> with <math>\delta(G) \ge d_0</math> satisfies <math>\chi'_g(G) \ge (1+\epsilon)\delta(G)</math>.'' <ref name=bevetal2008 />

== Incidence coloring game ==

The '''incidence coloring game''' is a graph coloring game, introduced by Andres,<ref name=Andres2009>{{harvtxt|Andres|2009a}}, see also erratum in {{harvtxt|Andres|2009b}}</ref> 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 <math>G</math>, denoted by <math>i_g(G)</math>, is the minimum number of colors needed for Alice to win this game on <math>G</math>.

For every graph <math>G</math> with maximum degree <math>\Delta</math>, we have <math>\frac{3\Delta - 1}{2} < i_g(G) < 3\Delta - 1</math>.<ref name=Andres2009/>

=== 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 <math>G</math> can be partitioned into two sets, one of them inducing a graph with arboricity <math>a</math>, the second inducing a graph with maximum degree <math>d</math>, then <math>i_g(G) \le \left\lfloor \frac{3\Delta(G) - a}{2} \right\rfloor + 8a + 3d - 1</math>.<ref name=charpSop2014>{{harvtxt|Charpentier|Sopena|2014}}, extending results of {{harvtxt|Charpentier|Sopena|2013}}.</ref> <br /> If moreover <math>\Delta(G) \ge 5a + 6d</math>, then <math>i_g(G) \le \left\lfloor \frac{3\Delta(G) - a}{2} \right\rfloor + 8a + d - 1</math>.<ref name=charpSop2014 /> * '''Degeneracy.''' If <math>G</math> is a ''k''-degenerated graph with maximum degree <math>\Delta(G)</math>, then <math>i_g(G) \le 2\Delta(G) + 4k - 2</math>. Moreover, <math>i_g(G) \le 2\Delta(G) + 3k - 1</math> when <math>\Delta(G) \ge 5k - 1</math> and <math>i_g(G) \le \Delta(G) + 8k - 2</math> when <math>\Delta(G) \le 5k -1</math>.<ref name=Andres2009/>

=== Graph Classes ===

For a class <math>{\mathcal C}</math> of graphs, we denote by <math>i_g({\mathcal C})</math> the smallest integer <math>k</math> such that every graph <math>G</math> of <math>{\mathcal C}</math> has <math>i_g(G) \le k</math>. * Paths : For <math>k \ge 13</math>, <math>i_g(P_k) = 5</math>. * Cycles : For <math>k \ge 3</math>, <math>i_g(C_k) = 5</math>.<ref>{{harvtxt|Kim|2011}}, improving a similar result for ''k ≥ 7'' in {{harvtxt|Andres|2009a}} (see also erratum in {{harvtxt|Andres|2009b}})</ref> * Stars : For <math>k \ge 1</math>, <math>i_g(S_{2k}) = 3k</math>.<ref name=Andres2009/> * Wheels : For <math>k \ge 6</math>, <math>i_g(W_{2k+1}) = 3k + 2</math>. For <math>k \ge 7</math>, <math>i_g(W_{2k}) = 3k</math>.<ref name=Andres2009/> * Subgraphs of Wheels : For <math>k \ge 13</math>, if <math>G</math> is a subgraph of <math>W_k</math> having <math>S_k</math> as a subgraph, then <math>i_g(G) = \left\lceil \frac{3k}{2} \right\rceil</math>.<ref>{{harvtxt|Kim|2011}}</ref>

=== Open Problems ===

* Is the upper bound <math>i_g(G) < 3\Delta(G) - 1</math> tight for every value of <math>\Delta(G)</math> ?<ref name=Andres2009/> * 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'') ?<ref name=Andres2009/>

== Notes ==

{{reflist|2}}

== References (chronological order) == {{refbegin}} * {{cite magazine | last = Gardner | first = Martin | date = 1981 | title = Mathematical Games |magazine= Scientific American | volume = 23 }} * {{cite book | last = Bodlaender | first = Hans L. | series = Lecture Notes in Computer Science | title = Graph-Theoretic Concepts in Computer Science | date = 1991 | chapter = On the complexity of some coloring games | volume = 484 | pages =30–40 | doi=10.1007/3-540-53832-1_29 | isbn = 978-3-540-53832-5 | citeseerx = 10.1.1.18.9992 }} * {{cite journal |last1 = Faigle |first1 = Ulrich |last2 = Kern |first2 = Walter |last3 = Kierstead |first3 = Henry A. |last4 = Trotter |first4 = William T. |authorlink4 = William T. Trotter |date = 1993 |title = On the Game Chromatic Number of some Classes of Graphs |url = http://people.math.gatech.edu/~trotter/papers/88.pdf |journal = Ars Combinatoria |volume = 35 |issue = 17 |pages = 143–150 |ref = {{harvid|Faigle et al.|1993}} |archive-date = 2014-06-06 |access-date = 2014-06-06 |archive-url = https://web.archive.org/web/20140606222924/http://people.math.gatech.edu/~trotter/papers/88.pdf |url-status = live }} * {{cite journal |last1 = Kierstead |first1 = Henry A. |last2 = Trotter |first2 = William T. |date = 1994 |title = Planar Graph Coloring with an Uncooperative Partner |url = http://people.math.gatech.edu/~trotter/papers/92.pdf |journal = Journal of Graph Theory |volume = 18 |issue = 6 |pages = 564–584 |doi = 10.1002/jgt.3190180605 |archive-date = 2014-07-14 |access-date = 2014-06-10 |archive-url = https://web.archive.org/web/20140714194722/http://people.math.gatech.edu/~trotter/papers/92.pdf |url-status = live }} * {{cite journal | last1 = Dinski | first1 = Thomas | last2 = Zhu | first2 = Xuding | date = 1999 | title = A bound for the game chromatic number of graphs | journal = Discrete Mathematics | volume = 196 | issue = 1–3 | pages =109–115 | doi=10.1016/s0012-365x(98)00197-6 | doi-access= free }} * {{cite journal | last1 = Guan | first1 = D. J. | last2 = Zhu | first2 = Xuding | date = 1999 | title = Game chromatic number of outerplanar graphs | journal = Journal of Graph Theory | volume = 30 | issue = 1 | pages =67–70 | doi=10.1002/(sici)1097-0118(199901)30:1<67::aid-jgt7>3.0.co;2-m }} * {{cite journal |last1 = Lam |first1 = Peter C. B. |last2 = Shiu |first2 = Wai C. |last3 = Xu |first3 = Baogang |date = 1999 |title = Edge game coloring of graphs |url = https://www.macalester.edu/~abeverid/papers/GameChIndex.pdf |journal = Graph Theory Notes N.Y. |volume = 37 |pages = 17–19 |archive-date = 2016-03-03 |access-date = 2014-07-07 |archive-url = https://web.archive.org/web/20160303225652/https://www.macalester.edu/~abeverid/papers/GameChIndex.pdf |url-status = live }} * {{cite journal | last = Zhu | first = Xuding | date = 1999 | title = The Game Coloring Number of Planar Graphs | journal = Journal of Combinatorial Theory, Series B | volume = 75 | issue = 2 | pages =245–258 | doi=10.1006/jctb.1998.1878 | doi-access= free }} * {{cite journal | last = Kierstead | first = Henry A. | date = 2000 | title = A Simple Competitive Graph Coloring Algorithm | journal = Journal of Combinatorial Theory, Series B | volume = 78 | issue = 1 | pages =57–68 | doi=10.1006/jctb.1999.1927 | doi-access= free }} * {{cite journal | last = Zhu | first = Xuding | date = 2000 | title = The game coloring number of pseudo partial ''k''-trees | journal = Discrete Mathematics | volume = 215 | issue = 1–3 | pages =245–262 | doi=10.1016/s0012-365x(99)00237-x | doi-access= }} * {{cite journal | last1 = Cai | first1 = Leizhen | last2 = Zhu | first2 = Xuding | date = 2001 | title = Game Chromatic Index of ''k''-Degenerate Graphs | journal = Journal of Graph Theory | volume = 36 | issue = 3 | pages =144–155 | doi=10.1002/1097-0118(200103)36:3<144::aid-jgt1002>3.0.co;2-f }} * {{cite journal | last1 = He | first1 = Wenjie | last2 = Hou | first2 = Xiaoling | last3 = Lih | first3 = Ko-Wei | last4 = Shao | first4 = Jiating | last5 = Wang | first5 = Weifan | last6 = Zhu | first6 = Xuding | date = 2002 | title = Edge-partitions of planar graphs and their game coloring numbers | journal = Journal of Graph Theory | volume = 41 | issue = 4 | pages =307–311 | ref = {{harvid|He et al.|2002}} | doi=10.1002/jgt.10069 | s2cid = 20929383 | doi-access= free }} * {{cite journal |last1 = Erdös |first1 = Peter L. |last2 = Faigle |first2 = Ulrich |last3 = Hochstättler |first3 = Winfried |last4 = Kern |first4 = Walter |date = 2004 |title = Note on the game chromatic index of trees |journal = Theoretical Computer Science |volume = 313 |issue = 3 |pages = 371–376 |ref = {{harvid|Erdös et al.|2004}} |doi = 10.1016/j.tcs.2002.10.002 |url = https://research.utwente.nl/en/publications/note-on-the-game-chromatic-index-of-trees(8dafd808-05bc-49f4-9bce-697ed8905fdc).html |doi-access = free }} * {{cite journal | last = Andres | first = Stephan D. | date = 2006 | title = The game chromatic index of forests of maximum degree Δ ⩾ 5 | journal = Discrete Applied Mathematics | volume = 154 | issue = 9 | pages =1317–1323 | doi=10.1016/j.dam.2005.05.031 | doi-access= }} * {{cite journal |last1 = Bartnicki |first1 = Tomasz |last2 = Grytczuk |first2 = Jaroslaw |last3 = Kierstead |first3 = H. A. |last4 = Zhu |first4 = Xuding |date = 2007 |title = The Map-Coloring Game |url = http://www.cs.umd.edu/~gasarch/TOPICS/graphcolgame/planar18.pdf |journal = American Mathematical Monthly |volume = 114 |issue = 9 |pages = 793–803 |jstor = 27642332 |ref = {{harvid|Bartnicki et al.|2007}} |doi = 10.1080/00029890.2007.11920471 |s2cid = 15901267 |archive-date = 2014-07-14 |access-date = 2014-07-09 |archive-url = https://web.archive.org/web/20140714135412/http://www.cs.umd.edu/~gasarch/TOPICS/graphcolgame/planar18.pdf |url-status = live }} * {{cite journal | last = Peterin | first = Iztok | date = 2007 | title = Game chromatic number of Cartesian product graphs | journal = Electronic Notes in Discrete Mathematics | volume = 29 | pages =353–357 | doi=10.1016/j.endm.2007.07.060 | citeseerx = 10.1.1.107.111 }} * {{cite journal |last = Sidorowicz |first = Elżbieta |date = 2007 |title = The game chromatic number and the game colouring number of cactuses |url = http://dl.acm.org/citation.cfm?id=1231795 |journal = Information Processing Letters |volume = 102 |issue = 4 |pages = 147–151 |doi = 10.1016/j.ipl.2006.12.003 |url-access = subscription }} * {{cite journal | last1 = Bartnicki | first1 = Tomasz | last2 = Grytczuk | first2 = Jarosław | date = 2008 | title = A Note on the Game Chromatic Index of Graphs | journal = Graphs and Combinatorics | volume = 24 | issue = 2 | pages =67–70 | doi=10.1007/s00373-008-0774-z | s2cid = 19373685 }} * {{cite journal | last1 = Beveridge | first1 = Andrew | last2 = Bohman | first2 = Tom | last3 = Friezeb | first3 = Alan | last4 = Pikhurko | first4 = Oleg | date = 2008 | title = Game chromatic index of graphs with given restrictions on degrees | journal = Theoretical Computer Science | volume = 407 | issue = 1–3 | pages =242–249 | doi=10.1016/j.tcs.2008.05.026 | doi-access= }} * {{cite journal | last = Zhu | first = Xuding | date = 2008 | title = Refined activation strategy for the marking game | journal = Journal of Combinatorial Theory, Series B | volume = 98 | issue = 1 | pages =1–18 | doi=10.1016/j.jctb.2007.04.004 | doi-access= free }} * {{cite journal | last = Andres | first = Stefan D. | date = 2009 | title = The incidence game chromatic number | journal = Discrete Applied Mathematics | volume = 157 | issue = 9 | pages =1980–1987 | ref = {{harvid|Andres|2009a}} | doi=10.1016/j.dam.2007.10.021 | doi-access= free }} * {{cite journal | last = Andres | first = Stefan D. | date = 2009 | title = Erratum to: The incidence game chromatic number | journal = Discrete Applied Mathematics | volume = 158 | issue = 6 |page=728 | ref = {{harvid|Andres|2009b}} | doi=10.1016/j.dam.2009.11.017 | doi-access= free }} * {{cite journal | last1 = Raspaud | first1 = André | first2 = Jiaojiao | last2 = Wu | date = 2009 | title = Game chromatic number of toroidal grids | journal = Information Processing Letters | volume = 109 | issue = 21–22 | pages =1183–1186 | doi=10.1016/j.ipl.2009.08.001 }} * {{cite journal |last = Sia |first = Charmaine |date = 2009 |title = The Game Chromatic Number of Some Families of Cartesian Product Graphs |url = http://www.math.harvard.edu/~sia/papers/game_chromatic_number_cartesian.pdf |archive-url = https://wayback.archive-it.org/all/20111114043919/http://www.math.harvard.edu/~sia/papers/game_chromatic_number_cartesian.pdf |url-status = dead |archive-date = 2011-11-14 |journal = AKCE International Journal of Graphs and Combinatorics |volume = 6 |issue = 2 |pages = 315–327 |access-date = 2014-07-16 }} * {{cite journal |last1 = Junosza-Szaniawski |first1 = Konstanty |last2 = Rożej |first2 = Łukasz |date = 2010 |title = Game chromatic number of graphs with locally bounded number of cycles |url = http://dl.acm.org/citation.cfm?id=1836461 |journal = Information Processing Letters |volume = 110 |issue = 17 |pages = 757–760 |doi = 10.1016/j.ipl.2010.06.004 |url-access = subscription }} * {{cite journal | last = Kim | first = John Y. | date = 2011 | title = The incidence game chromatic number of paths and subgraphs of wheels | journal = Discrete Applied Mathematics | volume = 159 | issue = 8 | pages =683–694 | doi=10.1016/j.dam.2010.01.001 | doi-access= free }} * {{cite book | last1 = Charpentier | first1 = Clément | last2 = Sopena | first2 = Éric | title = Combinatorial Algorithms | chapter = Incidence Coloring Game and Arboricity of Graphs | series = Lecture Notes in Computer Science | date = 2013 | volume = 8288 | pages =106–114 | doi=10.1007/978-3-642-45278-9_10 | arxiv= 1304.0166 | isbn = 978-3-642-45277-2 | s2cid = 14707501 }} * {{cite journal | last1 = Chan | first1 = Wai H. | last2 = Nong | first2 = Ge | date = 2014 | title = The game chromatic index of some trees of maximum degree 4 | journal = Discrete Applied Mathematics | volume = 170 | pages =1–6 | doi=10.1016/j.dam.2014.01.003 | doi-access= free }} * {{cite journal | last = Sekigushi | first = Yosuke | date = 2014 | title = The game coloring number of planar graphs with a given girth | journal = Discrete Mathematics | volume = 300 | pages =11–16 | doi=10.1016/j.disc.2014.04.011 | doi-access= }} * {{cite journal | last1 = Charpentier | first1 = Clément | last2 = Sopena | first2 = Éric | date = 2014 | title = The incidence game chromatic number of ''(a,d)''-decomposable graphs | journal = Journal of Discrete Algorithms | doi=10.1016/j.jda.2014.10.001 | volume=31 | pages=14–25 | s2cid = 1102795 | doi-access= }} * {{cite arXiv | last1 = Dunn | first1 = Charles | last2 = Larsen | first2 = Victor | last3 = Lindke | first3 = Kira | last4 = Retter | first4 = Troy | last5 = Toci | first5 = Dustin | date = 2014 | title = The game chromatic number of trees and forests | eprint = 1410.5223 | class = math.CO | ref = {{harvid|Dunn et al.|2014}} }} * {{cite journal |last1 = Costa |first1 = Eurinardo |last2 = Pessoa |first2 = Victor Lage |last3 = Soares |first3 = Ronan |last4 = Sampaio |first4 = Rudini |date = 2020 |title = PSPACE-completeness of two graph coloring games |journal = Theoretical Computer Science |volume = 824-825 |pages = 36–45 |doi = 10.1016/j.tcs.2020.03.022 |s2cid = 218777459 |ref = {{harvid|Costa, Pessoa, Soares, Sampaio|2020}} |doi-access= free }} * {{cite journal | last = Bradshaw | first = Peter | date = 2021 | title = Graph colorings with restricted bicolored subgraphs: II. The graph coloring game | journal = Journal of Graph Theory | volume = 100 | issue = 2 | pages = 371–383 | doi= 10.1002/jgt.22786 | arxiv= 2008.13275 | s2cid = 221377336 }} {{refend}}

Category:Graph coloring