Game colouring directed graphs

Daqing Yang ; Xuding Zhu

The electronic journal of combinatorics, Tome 17 (2010)

Résumé

In this paper, a colouring game and two versions of marking games (the weak and the strong) on digraphs are studied. We introduce the weak game chromatic number $\chi_{\rm wg}(D)$ and the weak game colouring number ${\rm wgcol}(D)$ of digraphs $D$. It is proved that if $D$ is an oriented planar graph, then $\chi_{\rm wg}(D)$ $\le {\rm wgcol}(D) \le 9$, and if $D$ is an oriented outerplanar graph, then $\chi_{\rm wg}(D)$ $\le {\rm wgcol}(D) \le 4$. Then we study the strong game colouring number ${\rm sgcol}\left( D \right)$ (which was first introduced by Andres as game colouring number) of digraphs $D$. It is proved that if $D$ is an oriented planar graph, then ${\rm sgcol}\left( D \right) \le 16$. The asymmetric versions of the colouring and marking games of digraphs are also studied. Upper and lower bounds of related parameters for various classes of digraphs are obtained.

Détail

DOI : 10.37236/283

Classification : 05C15, 05C20, 05C57
Mots-clés : dichromatic number, digraph, colouring game, directed graph marking game, planar graph