Acyclic Coloring - Upper Bounds

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)