Game chromatic index of k-degenerate graphs

We consider the following edge coloring game on a graph G. Given t distinct colors, two players Alice and Bob, with Alice moving first, alternately se lect an uncolored edge e of G and assign it a color different from the colo rs of edges adjacent to e. Bob wins if, at any stage of the game, there is an uncolored edge adjacent to colored edges in all t colors; otherwise Alic e wins. Note that when Alice wins, all edges of G are properly colored. The game chromatic index of a graph G is the minimum number of colors for whic h Alice has a winning strategy. in this paper, we study the edge coloring g ame on k-degenerate graphs. We prove that the game chromatic index of a k-d egenerate graph is at most Delta + 3k- 1, where Delta is the maximum vertex degree of the graph. We also show that the game chromatic index of a fores t of maximum degree 3 is at most 4 when the forest contains an odd number o f edges. (C) 2001 John Wiley & Sons. Inc.