The game chromatic index of some trees of maximum degree 4

The edge-coloring game on a graph with a given color set is a two-player game, in which Alice and Bob take turns (with Bob allowed to skip) to color an uncolored edge with a color from the given color set not assigned to any adjacent edges. Alice wins the game if all the edges of the graph are colored, while Bob wins if some uncolored edge does not have an available color. The game chromatic index of a graph G, , is the minimal cardinality of the given set of colors so that Alice has a winning strategy. It was proven that for any forest F of maximum degree Δ≠4, and the bound is sharp. The case of Δ=4 is still open. In this paper, we shall show that this bound, Δ+1, is also valid for the game chromatic index of forests of maximum degree 4 provided that each of their components is a caterpillar or contains no adjacent 4-vertices (vertices of degree 4). Copyright © 2014 Elsevier B.V.