Algorithmic aspects of acyclic edge colorings

A proper coloring of the edges of a graph G is called acyclic if there is no two-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) greater than or equal to Delta(G) + 2 where Delta(G) is the maximum degree in G. It is known that a'(G) less than or equal to Delta + 2 for almost all Delta-regular graphs, including all Delta-regular graphs whose girth is at least cDelta log Delta. We prove that determining the acyclic edge chromatic number of an arbitrary graph is an NP-complete problem, ror graphs G with sufficiently large girth in terms of Delta(G), we present deterministic polynomial-time algorithms that color the edges of G acyclically using at most Delta(G) + 2 colors.