ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2018-2019): c. 84%
Article in press
S.D. Andres, C. Charpentier, W.L. Fong
Game-perfect semiorientations of forests
Discussiones Mathematicae Graph Theory
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.
game chromatic number, game-perfect digraph, forest,
dichromatic number, game-perfect graph, forbidden induced subdigraph}