Acyclic coloring of graphs

Abstract

Abstract 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) = 0(d 4/3 ) as d → ∞. This settles a problem of Erdös who conjectured, in 1976, that A(G) = o(d 2 ) as d → ∞. We also show that there are graphs G with maximum degree d for which A(G) = Ω(d 4/3 /(log d) 1/3 ); and that the edges of any graph with maximum degree d can be colored by 0(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.