Acyclic chromatic number  Acyclic coloring  In graph theory, an
acyclic coloring is a (proper) vertex coloring in which every
2-chromatic subgraph is acyclic. The acyclic chromatic number
A(G) of a graph G is the least number of colors needed in any
acyclic coloring of G.  Some properties of A(G):    1. A(G) ≤ 2
if and only if G is acyclic.   2. A(G) ≤ 4 if Δ(G) = 3, where
Δ(G) is the maximum degree of G. (Grünbaum 1973)   3. A(G) ≤ 5
if Δ(G) = 4. (Burstein 1979)   4. It is NP-complete to determine
whether A(G) ≤ 3. (Kostochka 1978)  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 independen