Upper Bounds
A(G) ≤ 2 if and only if G is acyclic.
Bounds on A(G) in terms of the maximum degree Δ(G) of G include the following:
- A(G) ≤ 4 if Δ(G) = 3. (Grünbaum 1973)
- A(G) ≤ 5 if Δ(G) = 4. (Burstein 1979)
- A(G) ≤ 8 if Δ(G) = 5.
- A(G) ≤ 12 if Δ(G) = 6.
A milestone in the study of acyclic coloring is the following affirmative answer to a conjecture of Grünbaum:
Theorem. (Borodin 1979)
- A(G) ≤ 5 if G is planar graph.
Grünbaum (1973) introduced acyclic coloring and acyclic chromatic number, and conjectured the result in the above theorem. Borodin's proof involved several years of painstaking inspection of 450 reducible configurations. One consequence of this theorem is that every planar graph can be decomposed into an independent set and two forests. (Stein 1970, 1971)
Read more about this topic: Acyclic Coloring
Famous quotes containing the words upper and/or bounds:
“Give me the islands of the upper air,
all mountains
and the towering mountain trees.”
—Hilda Doolittle (1886–1961)
“Prohibition will work great injury to the cause of temperance. It is a species of intemperance within itself, for it goes beyond the bounds of reason in that it attempts to control a man’s appetite by legislation, and makes a crime out of things that are not crimes. A Prohibition law strikes a blow at the very principles upon which our government was founded.”
—Abraham Lincoln (1809–1865)