کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420338 | 683925 | 2010 | 10 صفحه PDF | دانلود رایگان |
We consider the following 2-person game which is played with an (initially uncolored) digraph DD, a finite color set CC, and nonnegative integers aa, bb, and dd. Alternately, player I colors aa vertices and player II colors bb vertices with colors from CC. Whenever a player colors a vertex vv, all in-arcs (w,v)(w,v) that do not come from a vertex ww previously colored with the same color as vv are deleted. For each color ii the defect digraph DiDi is the digraph induced by the vertices of color ii at a certain state of the game. The main rule the players have to respect is that at every time for any color ii the digraph DiDi has maximum total degree of at most dd. The game ends if no vertex can be colored any more according to this rule. Player I wins if DD is completely colored at the end of the game, otherwise player II wins. The smallest cardinality of a color set CC with which player I has a winning strategy for the game is called d-relaxed(a,b)-gamechromaticnumber of D. This parameter generalizes several variants of Bodlaender’s game chromatic number. We determine the tight (resp., nearly tight) upper bound ⌊bd+1⌋+2 (resp., ⌊bd+1⌋+3) for the dd-relaxed (a,b)(a,b)-game chromatic number of orientations of forests (resp., undirected forests) for any dd and a≥b≥1a≥b≥1. Furthermore we prove that these numbers cannot be bounded in case a
Journal: Discrete Applied Mathematics - Volume 158, Issue 4, 28 February 2010, Pages 251–260