Note on Acyclic Colorings of Graphs

Abstract

A vertex $k$-coloring of a graph $G$ is acyclic if no cycle is bichromatic. The minimum integer $k$ such that $G$ admits an acyclic $k$-coloring is called the acyclic chromatic number of $G$, denoted by ${\chi }_a(G)$. In this paper, we discuss some properties of maximal acyclic $k$-colorable graphs, prove a sharp lower bound of the ${\chi }_a(G)$ and get some results about the relation between $\chi (G)$ and ${\chi }_a(G)$. Furthermore, a conjecture of B. Grünbaum that ${\chi }_a(G)\le \mathrm{\Delta }+1$ is proved for maximal acyclic $k$-colorable graphs.