A new upper bound on the game chromatic index of graphs

We study the two-player game where Maker and Breaker alternately color the edges of a given graph G with k colors such that adjacent edges never get the same color. Maker's goal is to play such that at the end of the game, all edges are colored. Vice-versa, Breaker wins as soon as there is an uncolored edge where every color is blocked. The game chromatic index X-g(')(G) denotes the smallest k for which Maker has a winning strategy. The trivial bounds Delta(G) <= X-g(')(G) <= 2 Delta(G) - 1 hold for every graph G, where Delta(G) is the maximum degree of G. Beveridge, Bohman, Frieze, and Pikhurko conjectured that there exists a constant c > 0 such that for any graph G it holds X-g(')(G) <= (2-c)Delta(G) [Theoretical Computer Science 2008], and verified the statement for all delta > 0 and all graphs with Delta(G) >= (1/2 + delta)|V(G)|. In this paper, we show that x(g)(')(G) <= (2-c)Delta(G) is true for all graphs G with Delta(G) >= C log |V(G)|. In addition, we consider a biased version of the game where Breaker is allowed to color b edges per turn and give bounds on the number of colors needed for Maker to win this biased game.