کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427841 | 686565 | 2011 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: The game chromatic number and the game colouring number of classes of oriented cactuses The game chromatic number and the game colouring number of classes of oriented cactuses](/preview/png/427841.png)
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.
Journal: Information Processing Letters - Volume 111, Issue 5, 1 February 2011, Pages 222–226