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:
“The enemy are no match for us in a fair fight.... The young men ... of the upper class are kind-hearted, good-natured fellows, who are unfit as possible for the business they are in. They have courage but no endurance, enterprise, or energy. The lower class are cowardly, cunning, and lazy. The height of their ambition is to shoot a Yankee from some place of safety.”
—Rutherford Birchard Hayes (1822–1893)
“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)