AbstractAn 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⩽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. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 192–209, 2009