The Relaxed Game Chromatic Number Of Trees

The game chromatic number of a graph was introduced by Bodlaender[1] Recently, Chou, Wang and Zhu put forward a new concept-the relaxed game chromatic number of graph in [2]. This is a interesting definition in graph theory. It can connect coloring problem with game theory. The relaxed game chromatic number of a graph is defined through a two person game. Let G = (V, E) be a graph, k and d be positive integers. The (k, d)-relaxed coloring game is two persons, say Alice and Bob, alternately color the vertices of G with colors from a set X of k colors, with Alice having the first move. A color a E X is legal for an uncolored vertex v E V if by coloring v with a, the subgraph induced by all vertices of color a has maximum degree at most d. Each move of Alice or Bob colors an uncolored vertex with a legal color. Alice wins the game if all vertices of the graph are legally colored, otherwise Bob wins. Alice's goal is to produce a strategy so that she is able to win the game, and Bob's goal is to prevent this from happening. We define the d to be the defect degree. Then the d-relaxed game chromatic number of G, denoted by Xg(G), is the least number k of colors for which Alice has a winning strategy in the above coloring game.Nowadays, concerning the relaxed game chromatic number of tree, out-erplanar and partial k-tree graph have been studied by many researchers home and abroad, this paper studies further the relaxed game chromatic number of trees. It is proved by separation strategy that if G is a tree for d = 2, Xg(G) = 2. This result answers the question proposed by Dunn and Kierstead in [3].