2008/01/11 by Manu Basavaraju, Basavaraju, Manu, L. Sunil Chandran +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.0801.1744
13 pages
arxiv created 2008/01/11 · arxiv updated 2009/12/01
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). It was conjectured by Alon, Sudakov and Zaks that for any simple and finite graph G, a'(G)≤ Δ+2, where Δ=Δ(G) denotes the maximum degree of G. We prove the conjecture for connected graphs with Δ(G) ≤ 4, with the additional restriction that m ≤ 2n-1, where n is the number of vertices and m is the number of edges in G . Note that for any graph G, m ≤ 2n, when Δ(G) ≤ 4. It follows that for any graph G if Δ(G) ≤ 4, then a'(G) ≤ 7.