On acyclic colorings of graphs on surfaces (Q1916898)

A \(k\)-coloring of (the vertices of) a graph \(G\) is acyclic if every subgraph of \(G\) induced by any two color classes is a forest. The acyclic chromatic number of a surface \(S\) is the smallest number \(k\) such that every graph embeddable on \(S\) has an acyclic \(k\)-coloring. \textit{O. V. Borodin} [Discrete Math. 25, 211-236 (1979; Zbl 0406.05031)] proved a conjecture of B. Grünbaum that every planar graph has an acyclic 5-coloring and he also conjectured that the acyclic chromatic number of any surface other than the plane is the same as its chromatic number. This paper shows that the acyclic chromatic number of the projective plane is at most 7 and that of an arbitrary surface with Euler characteristic \(\chi=-\gamma\) is at most \(O(\gamma^{4/7})\). Moreover, there are graphs embeddable on surfaces of Euler characteristic \(\chi=-\gamma\) whose acyclic number is at least \(\Omega(\gamma^{4/7}/(\log\gamma)^{1/7})\). Thus Borodin's conjecture is false for all surfaces with large \(\gamma\).