Game chromatic index of graphs with given restrictions on degrees

Given a graph G and an integer k, two players alternatively color the edges of G using k colors so that adjacent edges get different colors. The game chromatic index is the minimum k for which the first player has a strategy that ensures that all edges of G get colored.The trivial bounds are , where Δ(G) denotes the maximal degree of G. Lam, Shiu, and Xu and, independently, Bartnicki and Grytczuk asked whether there is a constant C such that for every graph G. We show that the answer is in the negative by constructing graphs G such that and Δ(G)→∞. On the other hand, we show that for every μ>0 there is ε>0 such that for any graph G with Δ(G)≥(1/2+μ)v(G), we have , where v(G) denotes the number of vertices of G.