The edge coloring game on trees with the number of colors greater than the game chromatic index

摘要

Let X{A,B} and Y{A,B,-}, where A,B and - denote (player) Alice, (player) Bob and none of the players, respectively. In the k-[X,Y]-edge-coloring game, Alice and Bob alternately choose a color from a given color set with k colors to color an uncolored edge of a graph G such that no adjacent edges receive the same color. Player X begins and Player Y has the right to skip any number of turns. Alice wins the game if all the edges of G are finally colored; otherwise, Bob wins. The [X,Y]-game chromatic index of an uncolored graph G, denoted by [X,Y](G), is the least k such that Alice has a winning strategy for the game. We prove that, for any [X,Y], Alice has a winning strategy for the k-[X,Y]-edge-coloring game on any tree T when k>[X,Y](T). Moreover, using some parts of the proofs of the above results, we show that there is a tree T satisfying [A,-](T)<[B,-](T) and [A,-](T-e)<[B,-](T-e) for some edge e of T. This solves an open problem proposed by Andres et al. (Discrete Appl Math 159:1660-1665, 2011).