Improved bounds for acyclic chromatic index of planar graphs

AbstractAcyclic coloring problem is a specialized problem that arises in the efficient computation of Hessians. A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by χa′(G), is the least number of colors in an acyclic edge coloring of G. Let G be planar graphs with girth g and maximum degree Δ. In this paper, it is shown that if g≥4 and Δ≥8, then χa′(G)≤Δ+3; if g≥5 and Δ≥10 or g≥6 and Δ≥6, then χa′(G)=Δ