Acyclic vertex coloring of graphs of maximum degree 5

An acyclic vertex coloring of a graph is a proper vertex coloring such that there are no bichromatic cycles. The acyclic chromatic number of G , denoted a ( G ) , is the minimum number of colors required for acyclic vertex coloring of graph G . For a family F of graphs, the acyclic chromatic number of F , denoted by a ( F ) , is defined as the maximum a ( G ) over all the graphs G ∈ F . In this paper we show that a ( F ) = 8 where F is the family of graphs of maximum degree 5 and give a linear time algorithm to achieve this bound.