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 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 and rediscovered ten years after by Bodlaender. 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.
  3. If a vertex v is impossible to color properly, then Bob wins.
  4. 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, where is the chromatic number of and its maximum degree.
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:
  • Forests:. 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:.
  • Outerplanar graphs:.
  • Planar graphs:.
  • Planar graphs of given girth:,,,.
  • Toroidal grids: .
  • Partial k-trees:.
  • Interval graphs:, 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.
  • For a single edge we have:
  • For stars we have:
  • Trees:
  • Wheels: if
  • Complete bipartite graphs: if

    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 ?
''Relaxation of the previous question.''

Relations with other notions

  • Suppose a monotone class of graphs has bounded game chromatic number. Is it true that this class of graph has bounded game coloring number ?
  • Suppose a monotone class of graphs 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 is a forest, there exists such that and.
  • Let be the class of graphs such that for any, there exists such that and. What families of graphs are in ?

    Hypercubes

  • Is it true that for any hypercube ?
''It is known to be true for.''

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:
  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.
  3. If an edge e is impossible to color properly, 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, denoted by, is the minimum number of colors needed for Alice to win this game on.

General case

For every graph G,. 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.

This conjecture is true when is large enough compared to the number of vertices in.
  • Arboricity. Let be the arboricity of a graph. Every graph with maximum degree has.

    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:
  • Wheels: and when.
  • Forests : when, and.
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.

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

Incidence coloring game

The incidence coloring game is a graph coloring game, introduced by Andres, 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.
  3. If an incidence i is impossible to color properly, then Bob wins.
  4. 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.

Relations with other notions

  • '-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.
If moreover, then.
  • Degeneracy.' If is a k''-degenerated graph with maximum degree, then. Moreover, when and when.

    Graph Classes

For a class of graphs, we denote by the smallest integer such that every graph of has.
  • Paths : For,.
  • Cycles : For,.
  • Stars : For,.
  • Wheels : For,. For,.
  • Subgraphs of Wheels : For, if is a subgraph of having as a subgraph, then.

    Open Problems

  • Is the upper bound tight for every value of ?
  • Is the incidence game chromatic number a monotonic parameter ?