2009/08/16 by Manu Basavaraju, Basavaraju, Manu, L. Sunil Chandran +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.2 #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #cs.DM
paper · pdf · doi:10.48550/arxiv.0908.2237
10 pages. 0 figures
arxiv created 2009/08/16 · openalex publication_date 2009/08/16 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a'(G)≤ Δ+2, where Δ=Δ(G) denotes the maximum degree of the graph. We prove that if G is a planar graph with maximum degree Δ, then a'(G)≤ Δ+ 12.