Game chromatic index of k‐degenerate graphs

We consider the following edge coloring game on a graph G. Given tdistinct colors, two players Alice and Bob, with Alice moving first, alternately select an uncolored edge eof Gand assign it a color different from the colors 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 tcolors; otherwise Alice wins. Note that when Alice wins, all edges of Gare properly colored. The game chromatic indexof a graph Gis the minimum number of colors for which Alice has a winning strategy. In this paper, we study the edge coloring game on k‐degenerate graphs. We prove that the game chromatic index of a k‐degenerate graph is at most Δ + 3k− 1, where Δ is the maximum vertex degree of the graph. We also show that the game chromatic index of a forest of maximum degree 3 is at most 4 when the forest contains an odd number of edges. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 144–155, 2001