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.

Abstract

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.


Actions:
Download: [img] PDF - Preprinted Version
Download (242Kb) | Preview
Download: [img] Postscript - Preprinted Version
Download (487Kb) | Preview
Export as:
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
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/562