The relaxed game chromatic number of outerplanar graphs

The (r,d)-relaxed coloring game is played by two players, Alice and Bob, on a graph G with a set of r colors. The players take turns coloring uncolored vertices with legal colors. A color alpha is legal for an uncolored vertex u if u is adjacent to at most d vertices that have already been colored with alpha, and every neighbor of u that has already been colored with alpha is adjacent to at most d - 1 vertices that have already been colored with alpha. Alice wins the game if eventually all the vertices are legally colored; otherwise, Bob wins the game when there comes a time when there is no legal move left. We show that if G is outerplanar then Alice can win the (2,8)-relaxed coloring game on G. It is known that there exists an outerplanar graph G such that Bob can win the (2,4)-relaxed coloring game on G. (C) 2004 Wiley Periodicals, Inc.