Vladimir Yanovski, Israel A. Wagner, et al.
Ann. Math. Artif. Intell.
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(d4/3) as d → ∞. This settles a problem of Erdös who conjectured, in 1976, that A(G) = o(d2) as d → ∞. We also show that there are graphs G with maximum degree d for which A(G) = Ω(d4/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. Copyright © 1991 Wiley Periodicals, Inc., A Wiley Company
Vladimir Yanovski, Israel A. Wagner, et al.
Ann. Math. Artif. Intell.
Kafai Lai, Alan E. Rosenbluth, et al.
SPIE Advanced Lithography 2007
I.K. Pour, D.J. Krajnovich, et al.
SPIE Optical Materials for High Average Power Lasers 1992
A. Skumanich
SPIE OE/LASE 1992