ACYCLIC COLORING OF GRAPHS

A vertex coloring of a graph G is called acyclic if no two adjacent vertices have the same color and there is no two-colored cycle in G. The acyclic chromatic number of G, denoted by A(G), is the least number of colors in an acyclic coloring of G. We show that if G has maximum degree d, then A(G) = O(d4/3) as d --> infinity. This settles a problem of Erdos who conjectured, in 1976, that A(G) = o(d2) as d --> infinity. We also show that there are graphs G with maximum degree d for which A(G) = OMEGA(d4/3/(log d)1/3); and that the edges of any graph with maximum degree d can be colored by O(d) colors so that no two adjacent edges have the same color and there is no two-colored cycle. All the proofs rely heavily on probabilistic arguments.