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) \leq \Delta+1\) is proved for maximal acyclic \(k\)-colorable graphs.