Lightness of digraphs in surfaces and directed game chromatic number

Andres, Dominique (2009) 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. [11] 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 [3] resp Zhu [22] 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.

Download: [img] PDF - Preprinted Version
Download (248kB) | Preview
Download: [img] Postscript - Preprinted Version
Download (499kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2007-562
Depositing User: Dominique Andres
Date Deposited: 04 Dec 2007 00:00
Last Modified: 19 Dec 2011 09:44