Geodesic
Game-Perfect Semiorientations of Forests
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 501-534.

Voir la notice de l'article provenant de la source Library of Science

We consider digraph colouring games where two players, Alice and Bob, alternately colour vertices of a given digraph D with a colour from a given colour set in a feasible way. The game ends when such move is not possible any more. Alice wins if every vertex is coloured at the end, otherwise Bob wins. The smallest size of a colour set such that Alice has a winning strategy is the game chromatic number of D. The digraph D is game-perfect if, for every induced subdigraph H of D, the game chromatic number of H equals the size of the largest symmetric clique of H. In the strong game, colouring a vertex is feasible if its colour is different from the colours of its in-neighbours. In the weak game, colouring a vertex is feasible unless it creates a monochromatic directed cycle. There are six variants for each game, which specify the player who begins and whether skipping is allowed for some player. For all six variants of both games, we characterise the class of game-perfect semiorientations of forests by a set of forbidden induced subdigraphs and by an explicit structural description.
Keywords: game chromatic number, game-perfect digraph, forest, dichromatic number, game-perfect graph, forbidden induced subdigraph 
@article{DMGT_2022_42_2_a10,
     author = {Andres, Stephan Dominique and Charpentier, Cl\'ement and Fong, Wai Lam},
     title = {Game-Perfect {Semiorientations} of {Forests}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {501--534},
     publisher = {mathdoc},
     volume = {42},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a10/}
}
TY  - JOUR
AU  - Andres, Stephan Dominique
AU  - Charpentier, Clément
AU  - Fong, Wai Lam
TI  - Game-Perfect Semiorientations of Forests
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 501
EP  - 534
VL  - 42
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a10/
LA  - en
ID  - DMGT_2022_42_2_a10
ER  - 
%0 Journal Article
%A Andres, Stephan Dominique
%A Charpentier, Clément
%A Fong, Wai Lam
%T Game-Perfect Semiorientations of Forests
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 501-534
%V 42
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a10/
%G en
%F DMGT_2022_42_2_a10
Andres, Stephan Dominique; Charpentier, Clément; Fong, Wai Lam. Game-Perfect Semiorientations of Forests. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 501-534. http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a10/

[1] S.D. Andres, Lightness of digraphs in surfaces and directed game chromatic number, Discrete Math. 309 (2009) 3564–3579. https://doi.org/10.1016/j.disc.2007.12.060

[2] S.D. Andres, Asymmetric directed graph coloring games, Discrete Math. 309 (2009) 5799–5802. https://doi.org/10.1016/j.disc.2008.03.022

[3] S.D. Andres, Game-perfect graphs, Math. Methods Oper. Res. 69 (2009) 235–250. https://doi.org/10.1007/s00186-008-0256-3

[4] S.D. Andres, On characterizing game-perfect graphs by forbidden induced subgraphs, Contrib. Discrete Math. 7 (2012) 21–34. https://doi.org/10.11575/cdm.v7i1.62115

[5] S.D. Andres, Game-perfect digraphs, Math. Methods Oper. Res. 76 (2012) 321–341. https://doi.org/10.1007/s00186-012-0401-x

[6] S.D. Andres, On kernels in strongly game-perfect digraphs and a characterisation of weakly game-perfect digraphs, AKCE Int. J. Graphs Comb. 17 (2020) 539–549. https://doi.org/10.1016/j.akcej.2019.03.020

[7] S.D. Andres and W. Hochstättler, Perfect digraphs, J. Graph Theory 79 (2015) 21–29. https://doi.org/10.1002/jgt.21811

[8] S.D. Andres and E. Lock, Characterising and recognising game-perfect graphs, Discrete Math. Theor. Comput. Sci. 21 (2019) #6.

[9] J. Bang-Jensen and G.Z. Gutin, Digraphs: Theory, Algorithms and Applications (Springer, London, 2008). https://doi.org/10.1007/978-1-84800-998-1

[10] H.L. Bodlaender, On the complexity of some coloring games, Internat. J. Found. Comput. Sci. 2 (1991) 133–147. https://doi.org/10.1142/S0129054191000091

[11] E. Boros and V. Gurvich, Perfect graphs are kernel solvable, Discrete Math. 159 (1996) 35–55. https://doi.org/10.1016/0012-365X(95)00096-F

[12] W.H. Chan, W.C. Shiu, P.K. Sun and X. Zhu, The strong game colouring number of directed graphs, Discrete Math. 313 (2013) 1070–1077. https://doi.org/10.1016/j.disc.2013.02.001

[13] M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, The strong perfect graph theorem, Ann. of Math. (2) 164 (2006) 51–229. https://doi.org/10.4007/annals.2006.164.51

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

[15] M. Gardner, Mathematical games, Scientific American 244 (April, 1981) 23–26. https://doi.org/10.1038/scientificamerican0481-18

[16] Y. Guo and M. Surmacs, Miscellaneous digraph classes, in: Classes of Directed Graphs, J. Bang-Jensen, G. Gutin (Ed(s)), (Springer, Berlin, 2018) 517–574. https://doi.org/10.1007/978-3-319-71840-8_11

[17] E. Lock, The Structure of gB -Perfect Graphs (Bachelor’s Thesis FernUniversität, Hagen, 2016).

[18] V. Neumann-Lara, The dichromatic number of a digraph, J. Combin. Theory Ser. B 33 (1982) 265–270. https://doi.org/10.1016/0095-8956(82)90046-6

[19] Zs. Tuza and X. Zhu, Colouring games, in: Topics in Chromatic Graph Theory, L.W. Beineke and R.J. Wilson (Ed(s)), (Encyclopedia Math. Appl. 156 Cambridge Univ. Press, Cambridge, 2015) 304–326. https://doi.org/10.1017/CBO9781139519797.017

[20] D. Yang and X. Zhu, Game colouring directed graphs, Electron. J. Combin. 17 (2010) #R11. https://doi.org/10.37236/283

[21] X. Zhu, The game coloring number of planar graphs, J. Combin. Theory Ser. B 75 (1999) 245–258. https://doi.org/10.1006/jctb.1998.1878