Joy Y. Cheng, Daniel P. Sanders, et al.
SPIE Advanced Lithography 2008
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
Joy Y. Cheng, Daniel P. Sanders, et al.
SPIE Advanced Lithography 2008
Alfred K. Wong, Antoinette F. Molless, et al.
SPIE Advanced Lithography 2000
Corneliu Constantinescu
SPIE Optical Engineering + Applications 2009
Frank R. Libsch, Takatoshi Tsujimura
Active Matrix Liquid Crystal Displays Technology and Applications 1997