کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649843 | 1342467 | 2009 | 13 صفحه PDF | دانلود رایگان |

This paper investigates a competitive version of the coloring game on a finite graph GG. An asymmetric variant of the (r,d)(r,d)-relaxed coloring game is called the (r,d)(r,d)-relaxed (a,b)(a,b)-coloring game. In this game, two players, Alice and Bob, take turns coloring the vertices of a graph GG, using colors from a set XX, with |X|=r|X|=r. On each turn Alice colors aa vertices and Bob colors bb vertices. A color α∈Xα∈X is legal for an uncolored vertex uu if by coloring uu with color αα, the subgraph induced by all the vertices colored with αα has maximum degree at most dd. Each player is required to color an uncolored vertex legally on each move. The game ends when there are no remaining uncolored vertices. Alice wins the game if all vertices of the graph are legally colored, Bob wins if at a certain stage there exists an uncolored vertex without a legal color. The dd-relaxed (a,b)(a,b)-game chromatic number of GG, denoted (a,b)(a,b)-χgd(G), is the least rr for which Alice has a winning strategy in the (r,d)(r,d)-relaxed (a,b)(a,b)-coloring game.This paper extends the well-studied activation strategy of coloring games to relaxed asymmetric coloring games. The extended strategy is then applied to the (r,d)(r,d)-relaxed (a,1)(a,1)-coloring games on planar graphs, partial kk-trees and (s,t)(s,t)-pseudo-partial kk-trees. This paper shows that for planar graphs GG, if a≥2a≥2, then (a,1)(a,1)-χgd(G)≤6 for all d≥77d≥77. If HH is a partial kk-tree, 1≤a
Journal: Discrete Mathematics - Volume 309, Issue 10, 28 May 2009, Pages 3323–3335