2014/12/31 by Anton Bernshteyn
Computer Science · Mathematics · #Advanced Graph Theory Research #Bipartite graph #Combinatorics #Discrete mathematics #Edge coloring #Graph #Graph power #Lemma (botany) #Limits and Structures in Graph Theory #Line graph #Mathematics #Upper and lower bounds #math.CO
paper · pdf · doi:10.1016/j.disc.2016.05.002
published as Discrete Mathematics, vol. 339 (2016), n. 10, 2543--2552 · 12 pages, 2 figures. This version uses the Local Cut Lemma instead of the Local Action Lemma
openalex publication_date 2016/05/26 · arxiv created 2018/03/10 · arxiv updated 2018/03/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
An edge coloring of a graph G is called an acyclic edge coloring if it is proper and every cycle in G contains edges of at least three different colors. The least number of colors needed for an acyclic edge coloring of G is called the acyclic chromatic index of G and is denoted by a'(G). Fiamčik and independently Alon, Sudakov, and Zaks conjectured that a'(G) ≤ Δ(G)+2, where Δ(G) denotes the maximum degree of G. The best known general bound is a'(G)≤ 4(Δ(G)-1) due to Esperet and Parreau. We apply a generalization of the Lovász Local Lemma to show that if G contains no copy of a given bipartite graph H, then a'(G) ≤ 3Δ(G)+o(Δ(G)). Moreover, for every ε>0, there exists a constant c such that if g(G)≥ c, then a'(G)≤(2+ε)Δ(G)+o(Δ(G)), where g(G) denotes the girth of G.