Equality Perfect Graphs and Digraphs


  • Stephan Dominique Andres University of Greifswald, Institute of Mathematics and Computer Science, Germany




In the graph colouring game introduced by Bodlaender [7], two players, Alice and Bob, alternately colour uncoloured vertices of a given graph $G$ with one of $k$ colours so that adjacent vertices receive different colours. Alice wins if every vertex is coloured at the end. The game chromatic number of $G$ is the smallest $k$ such that Alice has a winning strategy.

In Bodlaender's original game, Alice begins. We also consider variants of this game where Bob begins or skipping turns is allowed [1] and their generalizations to digraphs [2]. By means of forbidden induced subgraphs (resp.\ forbidden induced subdigraphs), for several pairs $(g_1,g_2)$ of such graph (resp.\ digraph) colouring games $g_1$ and~$g_2$, which define game chromatic numbers $\chi_{g_1}$ and~$\chi_{g_2}$, we characterise the classes of graphs (resp.\ digraphs) such that, for any induced subgraph (resp.\ subdigraph)~$H$, the game chromatic numbers $\chi_{g_1}(H)$ and $\chi_{g_2}(H)$ of~$H$ are equal.


S.D. Andres, Lightness of digraphs in surfaces and directed game chromatic number. Discrete Math. 309 (2009), 3564--3579

S.D. Andres, Game-perfect graphs. Math. Methods Oper. Res. 69 (2009), 235--250

S.D. Andres, On characterizing game-perfect graphs by forbidden induced subgraphs. Contrib. Discrete Math. 7 (2012), 21--34

S.D. Andres, Game-perfect digraphs. Math. Methods Oper. Res. 76 (2012), 321--341

S.D. Andres and E. Lock, Characterising and recognising game-perfect graphs. Manuscript

T. Bartnicki, J. Grytczuk, H.A. Kierstead, and X. Zhu, The map-coloring game. Amer. Math. Monthly 114 (2007), 793--803

H.L. Bodlaender, On the complexity of some coloring games. Internat. J. Found. Comput. Sci. 2 (1991), 133--147

L. Cai and X. Zhu, Game chromatic index of $k$-degenerate graphs. J. Graph Theory 36 (2001), 144--155

C. Charpentier, The coloring game on planar graphs with large girth, by a result on sparse cactuses. Discrete Math. 340 (2017), 1069--1073

C. Charpentier, B. Effantin, and G. Paris, On the game coloring index of $F^+$-decomposable graphs. Discrete Appl. Math. 236 (2018), 73--83

C. Charpentier and E. Sopena, The incidence game chromatic number of $(a,d)$-decomposable graphs. J. Discrete Algorithms 31 (2015), 14--25

U. Faigle, W. Kern, H. Kierstead, and W.T. Trotter, On the game chromatic number of some classes of graphs. Ars Combin. 35 (1993), 143--150

M.C. Golumbic, Trivially perfect graphs. Discrete Math. 24 (1978), 105--107

D.J. Guan and X. Zhu, Game chromatic number of outerplanar graphs. J. Graph Theory 30 (1999), 67--70

H.A. Kierstead, A simple competitive graph coloring algorithm. J. Combin. Theory Ser. B 78 (2000), 57--68

J.W.H. Liu, The role of elimination trees in sparse factorization. SIAM J. Matrix Anal. Appl. 11 (1990), 134--172

E. Lock, The structure of $g_B$-perfect graphs. Bachelor's thesis, FernUniversität in Hagen, 2016

V. Neumann-Lara, The dichromatic number of a digraph. J. Combin. Theory Ser. B 33 (1982), 265--270

E. Sidorowicz, The game chromatic number and the game colouring number of cactuses, Inform. Process. Lett. 102 (2007), 147--151

E.S. Wolk, The comparability graph of a tree. Proc. Amer. Math. Soc. 13 (1962), 789--795

E.S. Wolk, A note on ``The comparability graph of a tree''. Proc. Amer. Math. Soc. 16 (1965), 17--20

J. Wu and X. Zhu, Lower bounds for the game colouring number of partial $k$-trees and planar graphs. Discrete Math. 308 (2008), 2637--2642

D. Yang and X. Zhu, Game colouring directed graphs. Electron. J. Combin. 17 (2010), R11

X. Zhu, The game coloring number of planar graphs. J. Combin. Theory Ser. B 75 (1999), 245--258

X. Zhu, The game coloring number of pseudo partial $k$-trees. Discrete Math. 215 (2000), 245--262

X. Zhu, Refined activation strategy for the marking game. J. Combin. Theory Ser. B 98 (2008), 1--18