Colouring games

MaRDI QIDQ2822601zbMATH OpenFDO

Authors Zsolt Tuza, Xuding Zhu

Publication date 30 September 2016

zbMATH Keywords

colouring gamegame chromatic numbergame colouring numbergame Grundy numberpaint number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving graphs (91A43)

Review text

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

Recommendations

• Impartial coloring games
• ON THE COMPLEXITY OF SOME COLORING GAMES
• scientific article; zbMATH DE number 139777
• Relaxed game chromatic number of graphs
• Asymmetric graph coloring games

Cited in

(22)

• Relaxed very asymmetric coloring games
• Graph labeling games
• Domination game on uniform hypergraphs
• Autotopism stabilized colouring games on rook's graphs
• Infinite chromatic games
• On game chromatic vertex-critical graphs
• Game-perfect semiorientations of forests
• Grundy coloring in some subclasses of bipartite graphs and their complements
• Indicated coloring game on Cartesian products of graphs
• The orthogonal colouring game
• Mr. Paint and Mrs. Correct
• A note on the connected game coloring number
• Transversal game on hypergraphs and the \(\frac{3}{4}\)-conjecture on the total domination game
• Bounds on the game transversal number in hypergraphs
• Impartial coloring games
• scientific article; zbMATH DE number 7316522 (Why is no real title available?)
• The coloring game on matroids
• scientific article; zbMATH DE number 5035591 (Why is no real title available?)
• Graph colorings with restricted bicolored subgraphs: II. The graph coloring game
• Indicated domination game
• The cordiality game and the game cordiality number
• Results on the graceful game and range-relaxed graceful game

This page was built for publication: Colouring games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2822601)