Acyclic coloring

Bounds on A(G) in terms of Δ(G), the maximum degree of G, include the following: A milestone in the study of acyclic coloring is the following affirmative answer to a conjecture of Grünbaum: 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 induced forests.

(Kostochka 1978) Coleman & Cai (1986) showed that the decision variant of the problem is NP-complete even when G is a bipartite graph.

Since chordal graphs can be optimally colored in O(n + m) time, the same is also true for acyclic coloring on that class of graphs.