Upper bounds on the acyclic chromatic index of degenerate graphs

Abstract

An acyclic edge coloring of a graph is a proper edge coloring without any bichromatic cycles. The acyclic chromatic index of a graph G denoted by a′(G), is the minimum k such that G has an acyclic edge coloring with k colors. Fiamčík [10] conjectured that a′(G)≤Δ+2 for any graph G with maximum degree Δ. A graph G is said to be k-degenerate if every subgraph of G has a vertex of degree at most k. Basavaraju and Chandran [4] proved that the conjecture is true for 2-degenerate graphs. We prove that for a 3-degenerate graph G, a′(G)≤Δ+5, thereby bringing the upper bound closer to the conjectured bound. We also consider k-degenerate graphs with k≥4 and give an upper bound for the acyclic chromatic index of the same. © 2024 Elsevier B.V.