Acyclic edge colorings of graphs

A proper coloring of the edges of a graph G is called acyclic if there is no 2‐colored cycle in G . The acyclic edge chromatic number of G , denoted by a′ ( G ), is the least number of colors in an acyclic edge coloring of G . For certain graphs G , a′ ( G ) ≥ Δ( G ) + 2 where Δ( G ) is the maximum degree in G . It is known that a′ ( G ) ≤ 16 Δ( G ) for any graph G . We prove that there exists a constant c such that a′ ( G ) ≤ Δ( G ) + 2 for any graph G whose girth is at least c Δ( G ) log Δ( G ), and conjecture that this upper bound for a′ ( G ) holds for all graphs G . We also show that a′ ( G ) ≤ Δ + 2 for almost all Δ‐regular graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 157–167, 2001