Juliann Opitz, Robert D. Allen, et al.
Microlithography 1998
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
Juliann Opitz, Robert D. Allen, et al.
Microlithography 1998
S.F. Fan, W.B. Yun, et al.
Proceedings of SPIE 1989
Jaione Tirapu Azpiroz, Alan E. Rosenbluth, et al.
SPIE Photomask Technology + EUV Lithography 2009
Leo Liberti, James Ostrowski
Journal of Global Optimization