Acyclic edge coloring of graphs with maximum degree 4

Abstract An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge 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 ⩽2 n −1, where n is the number of vertices and m is the number of edges in G . Note that for any graph G , m ⩽2 n , when Δ( G )⩽4. It follows that for any graph G if Δ( G )⩽4, then a ′( G )⩽7. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 192–209, 2009