Acyclic coloring of graphs with maximum degree 7 (Q2657099)

Let \(G\) be a finite, simple and connected graph with vertex set \(V(G)\) and edge set \(E(G)\). A proper \(k\)-coloring is a map \( \psi: V(G) \rightarrow \{ 1, 2, \ldots, k\}\) such that \(\psi(u) \neq \psi(v)\) for adjacent vertices \(u\) and \(v\). The acyclic chromatic number \(a(G)\) of \(G\) is the minimum number of colors for which \(G\) has a proper vertex coloring and no bichromatic cycles. For a graph \(G\) with maximum degree \(\Delta\), \textit{B. Grünbaum} [Isr. J. Math. 14, 390--408 (1973; Zbl 0265.05103)] conjectured that \(a(G) \le \Delta+1\). Up to now, this conjecture has been proven for \(\Delta \le 4\). In this paper, the authors show for \(\Delta=7\) that \(a(G) \le 12\) hereby improving the result \(a(G) \le 17\) of \textit{Y. Dieng}, \textit{H. Hocquard} and \textit{R. Naserasr} [``Acyclic coloring of graphs with maximum degree bounded'', in: Proceedings of the European conference on combinatorics, graph theory and applications, EuroComb'10 (2010)].