An Improved Bound of Acyclic Vertex-Coloring

Abstract

The acyclic chromatic number of a graph is the least number of colors needed to properly color its vertices so that none of its cycles has only two colors. We show that for all $\alpha >2^{-1/3}$ there exists an integer ${\Delta }_{\alpha }$ such that if the maximum degree $\Delta$ of a graph is at least ${\Delta }_{\alpha }$, then the acyclic chromatic number of the graph is at most $\lceil \alpha {\Delta }^{4/3}\rceil +\Delta +1$. The previous best bound, due to Gonçalves et al (2020), was $(3/2){\Delta }^{4/3}+O(\Delta )$.

Lemma 5 is wrong