×

Game colouring directed graphs. (English) Zbl 1215.05075

Summary: 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_{\text{wg}}(D)\) and the weak game colouring number \(\text{wgcol}(D)\) of digraphs \(D\). It is proved that if \(D\) is an oriented planar graph, then \(\chi_{\text{wg}}(D)\leq\text{wgcol}(D)\leq 9\), and if \(D\) is an oriented outerplanar graph, then \(\chi_{\text{wg}}(D)\leq\text{wgcol}(D)\leq 4\). Then we study the strong game colouring number \(\text{sgcol}(D)\) (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 \(\text{sgcol}(D)\leq 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.

MSC:

05C15 Coloring of graphs and hypergraphs
05C20 Directed graphs (digraphs), tournaments
05C57 Games on graphs (graph-theoretic aspects)