Directed defective asymmetric graph coloring games

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 froth 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 digraph D(i) 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 D(i) 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 wills if D is completely colored at the end of the game, otherwise player II wills. The smallest cardinality of a color set C with which player I has a winning strategy for the game is called d-relaxed (a, b)-game chromatic number of D. This parameter generalizes several variants of Bodlaender's game chromatic number. We determine the tight (resp., nearly tight) upper bound [b/d+1] + 2 (resp., [b/d+1] + 3) 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. (C) 2009 Elsevier B.V. All rights reserved.