This paper discusses the following two-person game on graphs. Let t, d be positive integers and X a set of colors with \X\ = t. Two persons, Alice and Bob, take turns coloring the vertices of G with colors from X, with Alice having the first move. A color c is feasible for an uncolored vertex x if by coloring x with color c, the subgraph of G induced by those vertices of color c has maximum degree at most d. Each move of Alice or Bob colors an uncolored vertex with a feasible color. The game is over if either all vertices of G are colored, or no more vertices can be colored with a feasiblecolor. Alice's goal is to produce a feasible coloring to color all the vertices of G, and Bob's goal is to prevent this from happening. By splitting the colored vertices of graphs,this paper proves that if G is a binary tree and d 2, then xG 2; if G is a forest and d 3, then x (G) 2. Let G is an outerplanar graph and d 2, G' is a 2-connected triangulation of G, if T is a path, then 5.Let G is an outerplanar graph and d 3, G' is a 2-connected triangulation of G and D is a minimum dominating set of TG, if TI(D] is a path, then Xg (G) 5. Moreover,this paper also discusses the game coloring of wheels and fans.
|