Graph coloring game

vertices of the graph.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 8 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

The game chromatic number \chi_g(G) is the minimum number of colors needed for Alice to win the vertex coloring game on G . For this graph, \chi_g(G)=3 , as it is the Cartesian product S_5 \square P_2 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.

Relation with other notions

Acyclic coloring. Every graph G with acyclic chromatic number k has \chi_g(G) \le k(k+1) . 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 .

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 .

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. Cactuses: \chi_g({\mathcal C}) = 5 .

Outerplanar graphs: 6 \le \chi_g({\mathcal O}) \le 7 . Planar graphs: 7 \le \chi_g({\mathcal P}) \le 17 . Planar graphs of given girth: \chi_g({\mathcal P}_4) \le 13 , \chi_g({\mathcal P}_5) \le 8 , \chi_g({\mathcal P}_6) \le 6 , \chi_g({\mathcal P}_8) \le 5 .

Toroidal grids: \chi_g({\mathcal TG}) = 5 . Partial k-trees: \chi_g({\mathcal T}_k) \le 3k+2 . 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.

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 . On the other hand, the game chromatic number of G \square H is bounded above by a function of \textrm{col}_g(G) and \textrm{col}_g(H) . In particular, if \textrm{col}_g(G) and \textrm{col}_g(H) are both at most t , then \chi_g(G \square H) \le t^5 - t^3 + t^2 .

For a single edge we have: \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: \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: \chi_g(T_1 \square T_2) \le 12. Wheels: \chi_g(P_2 \square W_n) = 5 if n \ge 9.

Complete bipartite graphs: \chi_g(P_2 \square K_{m,n}) = 5 if m, n \ge 5.

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

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 ?

Reducing maximum degree

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

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

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. There exists graphs with \chi'_g(G) > 1.008\Delta(G) for arbitrary large values of \Delta(G) . 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 . 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 .

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 .

Forests : \chi'_g({\mathcal F}_\Delta) \le \Delta + 1 when \Delta \ne 4 , and 5 \le \chi'_g({\mathcal F}_4) \le 6 . 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 . 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 ? 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) . Paths : For k \ge 13 , i_g(P_k) = 5 .

Cycles : For k \ge 3 , i_g(C_k) = 5 . Stars : For k \ge 1 , i_g(S_{2k}) = 3k . Wheels : For k \ge 6 , i_g(W_{2k+1}) = 3k + 2 . For k \ge 7 , i_g(W_{2k}) = 3k . 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 .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1324354446 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.