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:
“You doubt we read the stars on high,
Nathless we read your fortunes true;
The stars may hide in the upper sky,
But without glass we fathom you.”
—Ralph Waldo Emerson (18031882)
“How far men go for the material of their houses! The inhabitants of the most civilized cities, in all ages, send into far, primitive forests, beyond the bounds of their civilization, where the moose and bear and savage dwell, for their pine boards for ordinary use. And, on the other hand, the savage soon receives from cities iron arrow-points, hatchets, and guns, to point his savageness with.”
—Henry David Thoreau (18171862)