Graph coloring game

The vertex coloring game was introduced in 1981 by Steven Brams as a map-coloring game{{harvtxt|Gardner|1981}}{{harvtxt|Bartnicki et al.|2007}} and rediscovered ten years after by Bodlaender.{{harvtxt|Bodlaender|1991}} Its rules are as follows:

1. Alice and Bob color the vertices of a graph G with a set k of colors.
2. Alice and Bob take turns, coloring properly an 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 $\backslash 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 $\backslash chi(G)\; \backslash le\; \backslash chi\_g(G)\; \backslash le\; \backslash Delta(G)\; +\; 1$, where $\backslash chi(G)$ is the chromatic number of $G$ and $\backslash Delta(G)$ its maximum degree.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.

In the 1991 Bodlaender's paper,{{harvtxt|Bodlaender|1991}} the computational complexity was left as "an interesting open problem".

Only in 2020 it was proved that the game is PSPACE-Complete.{{harvtxt|Costa, Pessoa, Soares, Sampaio|2020}}

Acyclic coloring. Every graph $G$ with acyclic chromatic number $k$ has $\backslash chi\_g(G)\; \backslash le\; k(k+1)$.{{harvtxt|Dinski|Zhu|1999}}

Marking game. For every graph $G$, $\backslash chi\_g(G)\; \backslash 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 $\backslash chi\_g(G)\; \backslash le\; 4+c$.{{harvtxt|Junosza-Szaniawski|Rożej|2010}}

For a class $\{\backslash mathcal\; C\}$ of graphs, we denote by $\backslash chi\_g(\{\backslash mathcal\; C\})$ the smallest integer $k$ such that every graph $G$ of $\{\backslash mathcal\; C\}$ has $\backslash chi\_g(G)\; \backslash le\; k$. In other words, $\backslash chi\_g(\{\backslash 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: $\backslash chi\_g(\{\backslash mathcal\; F\})\; =\; 4$.{{harvtxt|Faigle et al.|1993}}, and implied by {{harvtxt|Junosza-Szaniawski|Rożej|2010}} Simple criteria are known to determine the game chromatic number of a forest without vertex of degree 3.{{harvtxt|Dunn et al.|2014}} It seems difficult to determine the game chromatic number of forests with vertices of degree 3, even for forests with maximum degree 3.
• Cactuses: $\backslash chi\_g(\{\backslash mathcal\; C\})\; =\; 5$.{{harvtxt|Sidorowicz|2007}}, and implied by {{harvtxt|Junosza-Szaniawski|Rożej|2010}}
• Outerplanar graphs: $6\; \backslash le\; \backslash chi\_g(\{\backslash mathcal\; O\})\; \backslash le\; 7$.{{harvtxt|Guan|Zhu|1999}}
• Planar graphs: $7\; \backslash le\; \backslash chi\_g(\{\backslash mathcal\; P\})\; \backslash le\; 17$.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}}.
• Planar graphs of given girth: $\backslash chi\_g(\{\backslash mathcal\; P\}\_4)\; \backslash le\; 13$,{{harvtxt|Sekigushi|2014}} $\backslash chi\_g(\{\backslash mathcal\; P\}\_5)\; \backslash le\; 8$, $\backslash chi\_g(\{\backslash mathcal\; P\}\_6)\; \backslash le\; 6$, $\backslash chi\_g(\{\backslash mathcal\; P\}\_8)\; \backslash le\; 5$.{{harvtxt|He et al.|2002}}
• Toroidal grids: $\backslash chi\_g(\{\backslash mathcal\; TG\})\; =\; 5$.{{harvtxt|Raspaud|Wu|2009}}
• Partial k-trees: $\backslash chi\_g(\{\backslash mathcal\; T\}\_k)\; \backslash le\; 3k+2$.{{harvtxt|Zhu|2000}}
• Interval graphs: $2\backslash omega\; \backslash le\; \backslash chi\_g(\{\backslash mathcal\; I\})\; \backslash le\; 3\backslash omega-2$, where $\backslash omega$ is for a graph the size of its largest clique.{{harvtxt|Faigle et al.|1993}}

Cartesian products.

The game chromatic number of the cartesian product $G\; \backslash square\; H$ is not bounded by a function of $\backslash chi\_g(G)$ and $\backslash 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 $\backslash chi\_g(K\_\{n,n\}\; \backslash square\; K\_\{m,m\})$ for arbitrary $n,\; m$.{{harvtxt|Peterin|2007}} On the other hand, the game chromatic number of $G\; \backslash square\; H$ is bounded above by a function of $\backslash textrm\{col\}\_g(G)$ and $\backslash textrm\{col\}\_g(H)$. In particular, if $\backslash textrm\{col\}\_g(G)$ and $\backslash textrm\{col\}\_g(H)$ are both at most $t$, then $\backslash chi\_g(G\; \backslash square\; H)\; \backslash le\; t^5\; -\; t^3\; +\; t^2$.{{harvtxt|Bradshaw|2021}}

• For a single edge we have:

::$\backslash 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}

• For stars we have:

::$\backslash 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}

• Trees: $\backslash chi\_g(T\_1\; \backslash square\; T\_2)\; \backslash le\; 12.$
• Wheels: $\backslash chi\_g(P\_2\; \backslash square\; W\_n)\; =\; 5$ if $n\; \backslash ge\; 9.$
• Complete bipartite graphs: $\backslash chi\_g(P\_2\; \backslash square\; K\_\{m,n\})\; =\; 5$ if $m,\; n\; \backslash ge\; 5.$

These questions are still open to this date.

{{hidden

|More colors for Alice {{harvtxt|Zhu|1999}}

|* 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.

|headerstyle=background:#ccccff

|style=text-align:center;

}}

{{hidden

|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 ?

• 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 ?

|headerstyle=background:#ccccff

|style=text-align:center;

}}

{{hidden

|Reducing maximum degree

|* Conjecture: Is $F$ is a forest, there exists $F\text{'}\; \backslash subseteq\; F$ such that $\backslash Delta(F\text{'})\; \backslash le\; \backslash chi\_g(F)$ and $\backslash chi\_g(F\text{'})\; =\; \backslash chi\_g(F)$.

• Let $\{\backslash mathcal\; G\}$ be the class of graphs such that for any $G\; \backslash in\; \{\backslash mathcal\; G\}$, there exists $G\text{'}\; \backslash subseteq\; G$ such that $\backslash Delta(G\text{'})\; \backslash le\; \backslash chi\_g(G)$ and $\backslash chi\_g(G\text{'})\; =\; \backslash chi\_g(G)$. What families of graphs are in $\{\backslash mathcal\; G\}$ ?

|headerstyle=background:#ccccff

|style=text-align:center;

}}

{{hidden

|Hypercubes

|* Is it true that $\backslash chi\_g(G)\; =\; n+1$ for any hypercube $Q\_n$ ?
It is known to be true for $n\; \backslash le\; 4$.

|headerstyle=background:#ccccff

|style=text-align:center;

}}

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

For every graph G, $\backslash chi\text{'}(G)\; \backslash le\; \backslash chi\text{'}\_g(G)\; \backslash le\; 2\backslash 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 $\backslash chi\text{'}\_g(G)\; >\; 1.008\backslash Delta(G)$ for arbitrary large values of $\backslash Delta(G)$.{{harvtxt|Beveridge|Bohman|Friezeb|Pikhurko|2008}}

Conjecture. There is an $\backslash epsilon\; >\; 0$ such that, for any arbitrary graph $G$, we have $\backslash chi\text{'}\_g(G)\; \backslash le\; (2-\backslash epsilon)\backslash Delta(G)$.

This conjecture is true when $\backslash Delta(G)$ is large enough compared to the number of vertices in $G$.

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

For a class $\{\backslash mathcal\; C\}$ of graphs, we denote by $\backslash chi\text{'}\_g(\{\backslash mathcal\; C\})$ the smallest integer $k$ such that every graph $G$ of $\{\backslash mathcal\; C\}$ has $\backslash chi\text{'}\_g(G)\; \backslash le\; k$. In other words, $\backslash chi\text{'}\_g(\{\backslash 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: $\backslash chi\text{'}\_g(W\_3)\; =\; 5$ and $\backslash chi\text{'}\_g(W\_n)\; =\; n+1$ when $n\backslash ge4$.
• Forests : $\backslash chi\text{'}\_g(\{\backslash mathcal\; F\}\_\backslash Delta)\; \backslash le\; \backslash Delta\; +\; 1$ when $\backslash Delta\; \backslash ne\; 4$, and $5\; \backslash le\; \backslash chi\text{'}\_g(\{\backslash mathcal\; F\}\_4)\; \backslash le\; 6$.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.
  Moreover, if every tree of a forest $F$ of $\{\backslash mathcal\; F\}\_4$ is obtained by subdivision from a caterpillar tree or contains no two adjacent vertices with degree 4, then $\backslash chi\text{'}\_g(F)\; \backslash le\; 5$.Conditions on forests with Δ=4 are in {{harvtxt|Chan|Nong|2014}}

Upper bound. Is there a constant $c\; \backslash ge\; 2$ such that $\backslash chi\text{'}\_g(G)\; \backslash le\; \backslash Delta(G)\; +\; c$ for each graph $G$ ? If it is true, is $c\; =\; 2$ enough ?

Conjecture on large minimum degrees. There are a $\backslash epsilon\; >\; 0$ and an integer $d\_0$ such that any graph $G$ with $\backslash delta(G)\; \backslash ge\; d\_0$ satisfies $\backslash chi\text{'}\_g(G)\; \backslash ge\; (1+\backslash epsilon)\backslash delta(G)$.

The incidence coloring game is a graph coloring game, introduced by Andres,{{harvtxt|Andres|2009a}}, see also erratum in {{harvtxt|Andres|2009b}} 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 $\backslash Delta$, we have .

• (a,d)-Decomposition. This is the best upper bound we know for the general case. If the edges of a graph $G$ can be partitioned 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)\; \backslash le\; \backslash left\backslash lfloor\; \backslash frac\{3\backslash Delta(G)\; -\; a\}\{2\}\; \backslash right\backslash rfloor\; +\; 8a\; +\; 3d\; -\; 1$.{{harvtxt|Charpentier|Sopena|2014}}, extending results of {{harvtxt|Charpentier|Sopena|2013}}.
  If moreover $\backslash Delta(G)\; \backslash ge\; 5a\; +\; 6d$, then $i\_g(G)\; \backslash le\; \backslash left\backslash lfloor\; \backslash frac\{3\backslash Delta(G)\; -\; a\}\{2\}\; \backslash right\backslash rfloor\; +\; 8a\; +\; d\; -\; 1$.
• Degeneracy. If $G$ is a k-degenerated graph with maximum degree $\backslash Delta(G)$, then $i\_g(G)\; \backslash le\; 2\backslash Delta(G)\; +\; 4k\; -\; 2$. Moreover, $i\_g(G)\; \backslash le\; 2\backslash Delta(G)\; +\; 3k\; -\; 1$ when $\backslash Delta(G)\; \backslash ge\; 5k\; -\; 1$ and $i\_g(G)\; \backslash le\; \backslash Delta(G)\; +\; 8k\; -\; 2$ when $\backslash Delta(G)\; \backslash le\; 5k\; -1$.

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

• Paths : For $k\; \backslash ge\; 13$, $i\_g(P\_k)\; =\; 5$.
• Cycles : For $k\; \backslash ge\; 3$, $i\_g(C\_k)\; =\; 5$.{{harvtxt|Kim|2011}}, improving a similar result for k ≥ 7 in {{harvtxt|Andres|2009a}} (see also erratum in {{harvtxt|Andres|2009b}})
• Stars : For $k\; \backslash ge\; 1$, $i\_g(S\_\{2k\})\; =\; 3k$.
• Wheels : For $k\; \backslash ge\; 6$, $i\_g(W\_\{2k+1\})\; =\; 3k\; +\; 2$. For $k\; \backslash ge\; 7$, $i\_g(W\_\{2k\})\; =\; 3k$.
• Subgraphs of Wheels : For $k\; \backslash ge\; 13$, if $G$ is a subgraph of $W\_k$ having $S\_k$ as a subgraph, then $i\_g(G)\; =\; \backslash left\backslash lceil\; \backslash frac\{3k\}\{2\}\; \backslash right\backslash rceil$.{{harvtxt|Kim|2011}}

• Is the upper bound tight for every value of $\backslash Delta(G)$ ?
• 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) ?

{{reflist|2}}

{{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}}

}}

• {{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

}}

• {{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

}}

• {{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

}}

• {{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

}}

• {{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

}}

• {{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

|url = https://doi.org/10.1016/j.tcs.2020.03.022

|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}}

}}

• {{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