Lightness of digraphs in surfaces and directed game chromatic number
Lightness of digraphs in surfaces and directed game chromatic number.
Published in: Discrete Mathematics Vol. 309 (11). pp. 3564-3579.
The lightness of a digraph is the minimum arc value, where the value of an arc is the maximum of the in-degrees of its terminal vertices. We determine upper bounds for the lightness of simple digraphs with minimum in-degree at least 1 (resp., graphs with minimum degree at least 2) and a given girth k, and without 4-cycles, which can be embedded in a surface S. (Graphs are considered as digraphs each arc having a parallel arc of opposite direction.) In case k is at least 5, these bounds are tight for surfaces of nonnegative Euler characteristics. This generalizes results of He et al.  concerning the lightness of planar graphs. From these bounds we obtain directly new bounds for the game coloring number, and thus for the game chromatic number of (di)graphs with girth k and without 4-cycles embeddable in S. The game chromatic resp. game coloring number were introduced by Bodlaender  resp Zhu  for graphs. We generalize these notions to arbitrary digraphs. We prove that the game coloring number of a directed simple forest is at most 3.
|Depositing User:||Dominique Andres|
|Date Deposited:||04 Dec 2007 00:00|
|Last Modified:||19 Dec 2011 09:44|