Game chromatic index of graphs with given restrictions on degrees

AbstractGiven 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 χg′(G) 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 Δ(G)≤χg′(G)≤2Δ(G)−1, 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 χg′(G)≤Δ(G)+C for every graph G. We show that the answer is in the negative by constructing graphs G such that χg′(G)≥1.008Δ(G) 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 χg′(G)≤(2−ε)Δ(G), where v(G) denotes the number of vertices of G