A new upper bound on the game chromatic index of graphs (Q1753125)

Summary: 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 \(\chi'_g(G)\) denotes the smallest \(k\) for which Maker has a winning strategy. The trivial bounds \(\Delta(G) \leq \chi_g'(G) \leq 2\Delta(G)-1\) hold for every graph \(G\), where \(\Delta(G)\) is the maximum degree of \(G\). \textit{A. Beveridge} et al. [Theor. Comput. Sci. 407, No. 1--3, 242--249 (2008; Zbl 1151.91029)] conjectured that there exists a constant \(c>0\) such that for any graph \(G\) it holds \(\chi'_g(G) \leq (2-c)\Delta(G)\), and verified the statement for all \(\delta>0\) and all graphs with \(\Delta(G) \geq (\frac12+\delta)|V(G)|\). In this paper, we show that \(\chi'_g(G) \leq (2-c)\Delta(G)\) is true for all graphs \(G\) with \(\Delta(G) \geq 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.