We compiled a list of references and an author index which you can find in our bibliography (pdf-file). Comments, corrections and additions are welcome.
Maker-breaker graph colouring games are non-cooperative games played by a maker, Alice, and a breaker, Bob. By certain rules, the players colour certain elements of the graph with a colour from a given colour set. Alice's goal is to achieve a graph where all considered elements of the graph are coloured. Bob tries to create a situation where some uncoloured elements cannot be coloured any more by the rules.
The most important parameter of this game is, for a graph
the smallest number of colours, so that Alice has a winning strategy for the game.
Usually, the rules are chosen in such a way that this parameter is
well-defined. So, if this parameter is
k, then Bob wins for all games with
k colours on
However, for some games it is not clear whether, if Alice
k colours, Alice wins on
G with more
There are various types of this game. The most important and oldest one is the vertex colouring game of an undirected graph. It was proposed by Brams in 1981 and reinvented by Bodlaender in 1991. Here, Alice and Bob alternately colour vertices of the graph, so that adjacent vertices receive distinct colours. The game ends if either all vertices are coloured (in which case Alice wins) or if there is an uncoloured vertex surrounded by vertices of all colours. The parameter defined by this game is called game chromatic number of the graph. The study of the game chromatic number for special classes of graphs was initiated by the work of Faigle et al. (1993). Obviously, the game chromatic number is a competitive version and an upper bound of the chromatic number of a graph.
In the game defining the game chromatic number, Alice has the first move.
The game where Bob has the first move may define a completely different
parameter. Consider the complete bipartite graph with
2n vertices and
delete a perfect matching in it (see figure above). The resulting graph has game
n (Bob may play according to a copycat strategy) but the
parameter for the game where Bob has the first move is only 2. The same
example can be used to show that, in general, the game chromatic number of
H of a graph
G is not necessarily smaller or equal to the game
chromatic number of
G. This is an example of Kierstead.
We will now list some other variants of games.
Here edges of a graph are coloured instead of vertices. The parameter defined hereby, the game chromatic index, is a game-theoretic analogon of the chromatic index. The edge colouring game was introduced by Cai and Zhu. It is the special case of the vertex colouring game for line graphs.
Here incidences of a graph are coloured instead of vertices. The parameter defined hereby, the incidence game chromatic number, is a game-theoretic analogon of the incidence colouring number. This game was introduced by me. It is the special case of the vertex colouring game for incidence graphs. (You might also be interested in The Incidence Coloring Page maintained by Eric Sopena.)
Here vertices of a digraph are coloured in such a way that an uncoloured vertex may not receive the colour of any of its in-neighbours. The parameter defined hereby, also called game chromatic number, is a game-theoretic analogon of the dichromatic number. Digraph colouring games were introduced by me. The vertex colouring game of a graph is a special case of these games since a graph is a digraph with pairs of antiparallel arcs.
Here, Alice and Bob do not necessarily colour one vertex in a move, but
there are numbers
b, so that Alice colours
a and Bob colours
vertices in a move. These games were introduced by Kierstead.
For all the afore-mentioned games one may define marking games. The parameter defined by the marking game associated with the ordinary colouring game is a game-theoretic analogon of the colouring number, and is called game colouring number. It was introduced by Zhu.
Here, vertices may have up to a certain number of neighbours with the same colour. The parameters defined hereby are competitive versions of relaxed graph colouring parameters. Relaxed graph colouring games were introduced by Chou et al.
Here, Bob may not use a colour that has not been used before, except if he is forced to do so. The parameter new game chromatic number was introduced by Chen et al.
This parameter is a game-theoretic analogon of the oriented chromatic number of an oriented graph. It was introduced by Nešetřil and Sopena.
Combinations of these games were considered, too.
© FernUniversität in Hagen – Diskrete Mathematik und
Webdesign und Programmierung: Heidrun Krimmel, Köln