Directed defective asymmetric graph coloring games |
| |
Authors: | Stephan Dominique Andres |
| |
Affiliation: | Department of Mathematics and Computer Science, FernUniversität in Hagen, Lützowstr. 125, 58084 Hagen, Germany |
| |
Abstract: | We consider the following 2-person game which is played with an (initially uncolored) digraph D, a finite color set C, and nonnegative integers a, b, and d. Alternately, player I colors a vertices and player II colors b vertices with colors from C. Whenever a player colors a vertex v, all in-arcs (w,v) that do not come from a vertex w previously colored with the same color as v are deleted. For each color i the defect digraphDi is the digraph induced by the vertices of color i at a certain state of the game. The main rule the players have to respect is that at every time for any color i the digraph Di has maximum total degree of at most d. The game ends if no vertex can be colored any more according to this rule. Player I wins if D is completely colored at the end of the game, otherwise player II wins. The smallest cardinality of a color set C with which player I has a winning strategy for the game is called . This parameter generalizes several variants of Bodlaender’s game chromatic number. We determine the tight (resp., nearly tight) upper bound (resp., ) for the d-relaxed (a,b)-game chromatic number of orientations of forests (resp., undirected forests) for any d and a≥b≥1. Furthermore we prove that these numbers cannot be bounded in case a<b. |
| |
Keywords: | Digraph coloring game Dichromatic number Game chromatic number Relaxed coloring Defect Asymmetric coloring Directed forest |
本文献已被 ScienceDirect 等数据库收录! |
|