### Abstract

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) |
---|---|

Pages (from-to) | 273-283 |

Number of pages | 11 |

Journal | Israel Journal of Mathematics |

Volume | 94 |

DOIs | |

State | Published - Jan 1 1996 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Mathematics(all)

## Fingerprint Dive into the research topics of 'On acyclic colorings of graphs on surfaces'. Together they form a unique fingerprint.

## Cite this

*Israel Journal of Mathematics*,

*94*, 273-283. https://doi.org/10.1007/BF02762708