Journal of Combinatorics

Volume 7 (2016)

Number 4

A note on acyclic vertex-colorings

Pages: 725 – 737

DOI: http://dx.doi.org/10.4310/JOC.2016.v7.n4.a8

Authors

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)

Abstract

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.

Keywords

acyclic coloring, entropy compression, local lemma

Full Text (PDF format)