2012/09/12 by Wang Weifan, Weifan Wang, Qiaojun Shu +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1209.2471
24 pages, 9 figures
arxiv created 2012/09/12 · openalex publication_date 2012/09/12 · arxiv updated 2012/09/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index a'(G) of G is the smallest integer k such that G has an acyclic edge coloring using k colors. Fiam\rm \checkcik (1978) and later Alon, Sudakov and Zaks (2001) conjectured that a'(G)≤ Δ+ 2 for any simple graph G with maximum degree Δ. Basavaraju and Chandran (2009) showed that every graph G with Δ=4, which is not 4-regular, satisfies the conjecture. In this paper, we settle the 4-regular case, i.e., we show that every 4-regular graph G has a'(G)≤ 6.