An acyclic analogue to Heawood's theorem
Michael O. Albertson, David Monty Berman · Glasgow Mathematical Journal · 1978
The concept of acyclic coloring was introduced by Grünbaum [5] and is a generalization of point arboricity. A proper k -coloring of the vertices of a graph G is said to be acyclic if G contains no two-colored cycle. The acyclic chromatic number of a graph G , denoted by a ( G ), is the minimum value of k for which G has an acyclic k -coloring. Let a ( n ) denote the maximum value of the acyclic chromatic number among all graphs of genus n . In [5], Grünbaum conjectured that a (0) = 5 and proved that a (0)≤9. The conjecture was proved by Borodin [ 3 ] after the upper bound was improved three times in [ 7 ], [ 1 ] and [ 6 ]. In [ 2 ], we proved that a (1)≤ a (0) + 3. The purpose of this paper is to prove the following Theorem. Any graph of genus n>0 can be acyclically colored with 4 n + 4 colors . It is not known for any n >0 whether a ( n )> H ( n ), the Heawood number [ 8 ].