ON ACYCLIC COLORINGS OF GRAPHS ON SURFACES

A proper k-coloring of a graph is acyclic if every 2-chromatic subgrap h is acyclic. Borodin showed that every planar graph has an acyclic 5- coloring. This paper shows that the acyclic chromatic number of the pr ojective plane is at most 7. The acyclic chromatic number of an arbitr ary surface with Euler characteristic chi = -gamma is at most O(gamma( 4/7)). This is nearly tight; for every gamma > 0 there are graphs embe ddable on surfaces of Euler characteristic -gamma whose acyclic chroma tic number is at least Omega(gamma(4/7)/(log gamma)(1/7)). Therefore, the conjecture of Borodin that the acyclic chromatic of any surface bu t the plane is the same as its chromatic number is false for all surfa ces with large gamma (and may very well be false for all surfaces).