Game-perfect semiorientations of forests

Stephan Dominique ANDRES, Clément CHARPENTIER, Wai Lam FONG

Research output: Contribution to journalArticlespeer-review


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. Copyright © 2020 Stephan Dominique Andres et al., published by Sciendo.
Original languageEnglish
Pages (from-to)501-534
JournalDiscussiones Mathematicae - Graph Theory
Issue number2
Early online dateApr 2020
Publication statusPublished - 2022


Andres, S. D., Charpentier, C., & Fong, W. L. (2022). Game-perfect semiorientations of forests. Discussiones Mathematicae - Graph Theory, 42(2), 501-534. doi: 10.7151/dmgt.2302


  • Game chromatic number
  • Game-perfect digraph
  • Forest
  • Dichromatic number
  • Game-perfect graph
  • Forbidden induced subdigraph
  • PG student publication


Dive into the research topics of 'Game-perfect semiorientations of forests'. Together they form a unique fingerprint.