- Journal Article
Rights / licenseCreative Commons Attribution-NoDerivatives 4.0 International
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 χ′g(G) denotes the smallest k for which Maker has a winning strategy. The trivial bounds Δ(G)≤χ′g(G)≤2Δ(G)−1 hold for every graph G, where Δ(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 χ′g(G)≤(2−c)Δ(G) [Theoretical Computer Science 2008], and verified the statement for all δ>0 and all graphs with Δ(G)≥(12+δ)|V(G)|. In this paper, we show that χ′g(G)≤(2−c)Δ(G) is true for all graphs G with Δ(G)≥Clog|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 Show more
External linksSearch via SFX
Journal / seriesThe Electronic Journal of Combinatorics
Pages / Article No.
MoreShow all metadata