Trees of minimum order with game chromatic index equal ∆+1

In an edge-coloring game, Alice and Bob take turns to pick one color in a given color set and put it on one of the uncolored edges of a graph G so that no adjacent edges will receive the same color. Bob makes the first move and he is allowed to skip his moves while Alice is not. Alice needs to color all the edges of G to win the game while Bob tries to make one uncolored edge surrounded by all colors in the given color on its adjacent edges. The least number of colors required in the given color set so that Alice can have a strategy to win the game on G is called the game chromatic index of G. It is known that, for most of trees, the game chromatic index is equal to their maximum degrees, ∆, or ∆+1. In this paper, we shall show that the minimum order of trees with game chromatic index equal to ∆+1 is 3∆-1. Copyright © 2014 Utilitas Mathematica Pub. Inc.