2008/03/17 by Manu Basavaraju, Basavaraju, Manu, L. Sunil Chandran +1
Computer Science · Mathematics · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO #msc:05C15
paper · pdf · doi:10.48550/arxiv.0803.2433
21 pages, 3 figures
openalex publication_date 2008/03/17 · arxiv created 2008/10/20 · 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 cycle s. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic e dge coloring using k colors and is denoted by a'(G). A graph is called 2-degenerate if any of its induced subgraph has a vertex of degree at most 2. The class of 2-degenerate graphs properly conta in series-parallel graphs, outerplanar graphs, non-regular subcubic graphs, planar graphs of girth at least 6 and circle graphs of girth at least 5 as subclasses. It was conjectur ed by Alon, Sudakov and Zaks (and earlier by Fiamcik) that a'(G)≤ Δ+2, where Δ=Δ(G) denotes the maximum deg ree of the graph. We prove the conjecture for 2-degenerate graphs: in fact we prove a stronger bound . We prove that if G is a 2-degenerate graph with maximum degree Δ, then a'(G)≤ Δ+ 1.