Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
427841 | Information Processing Letters | 2011 | 5 Pages |
We prove that the game chromatic and the game colouring number of the class of orientations of cactuses with girth of 2 or 3 is 4. We improve this bound for the class of orientations of certain forest-like cactuses to the value of 3. These results generalise theorems on the game colouring number of undirected forests (Faigle et al., 1993 [3]) resp. orientations of forests (Andres, 2009 [1]). For certain undirected cactuses with girth 4 we also obtain the tight bound 4, thus improving a result of Sidorowicz (2007) [8].
Research highlights► We consider colouring games for digraphs and their game colouring numbers (gcn). ► We examine the gcn of classes of orientations of cactuses. ► The gcn of the class of orientations of cactuses of girth 2 or 3 is 4. ► The gcn of directed cactus trees is at most 3. ► The gcn of undirected forests with thin 4-cycles is at most 4.