Upper bounds on the acyclic chromatic index of degenerate graphs

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. Fiamcik [10] conjectured that a'(G) <= Delta + 2 for any graph G with maximum degree Delta. 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) <= Delta + 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. (c) 2024 Elsevier B.V. All rights reserved.