A proper k-coloring of a graph is acyclic if every 2-chromatic subgraph is acyclic. Borodin showed that every planar graph has an acyclic 5-coloring. This paper shows that the acyclic chromatic number of the projective plane is at most 7. The acyclic chromatic number of an arbitrary surface with Euler characteristic χ = -γ is at most O(γ4/7). This is nearly tight; for every γ > 0 there are graphs embeddable on surfaces of Euler characteristic -γ whose acyclic chromatic number is at least Ω(γ4/7/(log γ)1/7). Therefore, the conjecture of Borodin that the acyclic chromatic number of any surface but the plane is the same as its chromatic number is false for all surfaces with large γ (and may very well be false for all surfaces).
|Original language||English (US)|
|Number of pages||11|
|Journal||Israel Journal of Mathematics|
|State||Published - 1996|
All Science Journal Classification (ASJC) codes