Journal of Combinatorics

Volume 7 (2016)

Number 4

A note on acyclic vertex-colorings

Pages: 725 – 737



Jean-Sébastien Sereni (Centre National de la Recherche Scientifique, LORIA, Vandoeuvre-lès-Nancy, France)

Jan Volec (Department of Mathematics, ETH Zürich, Switzerland)


We prove that the acyclic chromatic number of a graph with maximum degree $\Delta$ is less than $2.835\Delta^{4/3} + \Delta$. This improves the previous upper bound, which was $50\Delta^{4/3}$. To do so, we draw inspiration from works by Alon, McDiarmid and Reed, and by Esperet and Parreau.


acyclic coloring, entropy compression, local lemma

Full Text (PDF format)