Sách Game colouring directed graphs

Abstract
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 χwg(D) and the weak game colouring number wgcol(D) of digraphs D. It is
proved that if D is an oriented planar graph, then χwg(D) 6 wgcol(D) 6 9, and if D
is an oriented outerplanar graph, then χwg(D) 6 wgcol(D) 6 4. Then we study the
strong game colouring number 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 sgcol (D) 6 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.