14 - Colouring games

Summary

There are various kinds of two-person games in which the players construct a colouring of a graph (or of a subgraph), and some additional games are closely related to graph colourings. Here we describe several variants, most of which deal with ‘maker–breaker games’. We also consider the game version of list-colourings.

Introduction

The connection between graph colourings and game theory has its roots in the works of P. M. Grundy in the latter field as early as the 1930s. His research later motivated the introduction of some graph invariants, one of which is discussed in detail in Berge's monograph [9]. For undirected graphs the analogous parameter is the Grundy number, also called the online chromatic number, which we will consider in Section 9. But although Grundy colouring may be formulated in terms of games, it remains a solitaire game in which the player aims at finding a solution that is as bad as possible.

In this chapter we mainly consider non-cooperative two-person games that either construct colourings or are otherwise closely related to some kind of colouring concept, even when they do not colour the graph.

A good starting point is the following maker–breaker game, which was introduced by Brams [24] for planar graphs in 1981, and independently by Bodlaender [12] for general graphs in 1991. Given a graph G, two players alternately colour vertices of G from a set of colours, say {1, 2, …, k}. The two players are Alice (the maker) and Bob (the breaker); each of them colours one uncoloured vertex at a time, under the condition that monochromatic edges must not occur, Alice moving first. Alice wins if a proper k-colouring of the entire graph G is eventually obtained, whereas Bob wins if a situation is reached where the neighbourhood of some uncoloured vertex contains all the k colours of the palette. Certainly, if the number of colours is sufficiently large (for example, if k = |V(G)|), then Alice surely wins the game.