Colouring games (Q2822601)

This chapter gives an overview on various kinds of colouring games. The authors consider games in which the players construct a colouring of a graph, including the relaxed colouring game, asymmetric colouring game, the marking game, the greedy colouring game. The authors also discuss the list-coluring version of the game -- the \(f\)-painting game. Furthermore, the games that are closely related to graph colourings: achievement and avoidance games and the acyclic orientation game are considered. This chapter surveys the main known results on chromatic numbers related with these game. Moreover, the authors present some methods of proofs that are frequently used to establish bounds on games chromatic numbers. In addition, algorithmic complexity of the games is discussed.NEWLINENEWLINEFor the entire collection see [Zbl 1317.05004].