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) |