On acyclic colorings of graphs on surfaces

Noga Alon, Bojan Mohar, Daniel P. Sanders

Research output: Contribution to journalArticlepeer-review

36 Scopus citations


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 languageEnglish (US)
Pages (from-to)273-283
Number of pages11
JournalIsrael Journal of Mathematics
StatePublished - 1996
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Mathematics


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

Cite this