
arXiv: 1710.01472
handle: 20.500.11850/282029
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) \le \chi_g'(G) \le 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 $\chi'_g(G) \le (2-c)\Delta(G)$ [Theoretical Computer Science 2008], and verified the statement for all $\delta>0$ and all graphs with $\Delta(G) \ge (\frac12+\delta)|V(G)|$. In this paper, we show that $\chi'_g(G) \le (2-c)\Delta(G)$ is true for all graphs $G$ with $\Delta(G) \ge 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.
random strategies, Games on graphs (graph-theoretic aspects), edge colorings, games on graphs, 05C57, 91A46, G.2.1, G.2.2, game chromatic index, Coloring of graphs and hypergraphs, G.2.1; G.2.2, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Games involving graphs
random strategies, Games on graphs (graph-theoretic aspects), edge colorings, games on graphs, 05C57, 91A46, G.2.1, G.2.2, game chromatic index, Coloring of graphs and hypergraphs, G.2.1; G.2.2, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Games involving graphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
