On acyclic colorings of graphs on surfaces
type: Item
instance of: scholarly article
title: On acyclic colorings of graphs on surfaces
zbMATH Open document ID: 0857.05033
DOI: 10.1007/BF02762708
author: Noga Alon
author: Bojan Mohar
author: Daniel P. Sanders
published in: Israel Journal of Mathematics
publication date: 1997-03-06T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 902625
zbMATH Keywords: acyclic colorings
zbMATH Keywords: acyclic chromatic number
zbMATH Keywords: surface
zbMATH Keywords: chromatic number
zbMATH Keywords: projective plane
zbMATH Keywords: Euler characteristic
zbMATH Keywords: Borodin's conjecture
reviewed by: H. P. Yap
MaRDI profile type: Publication
cites work: Q4111593
cites work: Every planar graph has an acyclic 7-coloring
cites work: An acyclic analogue to Heawood's theorem
cites work: Acyclic coloring of graphs
cites work: Q4004078
cites work: On acyclic colorings of planar graphs
cites work: Acyclic colorings of planar graphs
cites work: Q4200238
cites work: Note to the paper of Grünbaum on acyclic colorings
cites work: Every planar graph has an acyclic 8-coloring
cites work: SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEM
cites work: Q4857375
cites work: Note on a paper of B. Grünbaum on acyclic colorings
full work available at URL: https://doi.org/10.1007/bf02762708
OpenAlex ID: W2061409357
description: scientific article; zbMATH DE number 902625