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.
The vertex coloring game was introduced in 1981 by Steven Brams as a map-coloring game[1][2] and rediscovered ten years after by Bodlaender.
[3] Its rules are as follows: The game chromatic number of a graph
, is the minimum number of colors needed for Alice to win the vertex coloring game on
[4] In the 1991 Bodlaender's paper,[5] the computational complexity was left as "an interesting open problem".
Only in 2020 it was proved that the game is PSPACE-Complete.
with acyclic chromatic number
Almost every known upper bound for the game chromatic number of graphs are obtained from bounds on the game coloring number.
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: Cartesian products.
The game chromatic number of the cartesian product
In particular, the game chromatic number of any complete bipartite graph
is equal to 3, but there is no upper bound for
[19] On the other hand, the game chromatic number of
[20] These questions are still open to this date.
The edge coloring game, introduced by Lam, Shiu and Zu,[23] 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: 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
, is the minimum number of colors needed for Alice to win this game on
There are graphs reaching these bounds but all the graphs we know reaching this upper bound have small maximum degree.
for arbitrary large values of
is large enough compared to the number of vertices in
is the exact upper bound for the game chromatic index of graphs in this class.
[23] Conjecture on large minimum degrees.
[24] The incidence coloring game is a graph coloring game, introduced by Andres,[28] 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: The incidence game chromatic number of a graph
, is the minimum number of colors needed for Alice to win this game on