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). Copyright © 2019 Springer Science+Business Media, LLC, part of Springer Nature.