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:
“If the upper beams are not straight, the lower beams will be crooked.”
—Chinese proverb.
“Firmness yclept in heroes, kings and seamen,
That is, when they succeed; but greatly blamed
As obstinacy, both in men and women,
Whene’er their triumph pales, or star is tamed —
And ‘twill perplex the casuist in morality
To fix the due bounds of this dangerous quality.”
—George Gordon Noel Byron (1788–1824)