Game chromatic index of \(k\)-degenerate graphs (Q2712591)

The game chromatic index of a graph \(G\) is the minimum number of colors for which the first player has a winning strategy in the following game. Alternatingly, the players select an edge and color it with a color, different from colors already given to incident edges. The first player wins when the entire graph is colored. This paper shows that the game chromatic index of a \(k\)-degenerate graph (i.e., a graph such that every induced subgraph has a vertex of degree at most \(k\)) is at most \(\Delta + 3k-1\), \(\Delta\) the maximum degree of a vertex. The game chromatic index of a forest of maximum degree 3 is at most 4 when the forest contains an odd number of edges.