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 GG, denoted a(G)a(G), is the minimum number of colors required for acyclic vertex coloring of graph GG. For a family FF of graphs, the acyclic chromatic number of FF, denoted by a(F)a(F), is defined as the maximum a(G)a(G) over all the graphs G∈FG∈F. In this paper we show that a(F)=8a(F)=8 where FF is the family of graphs of maximum degree 5 and give a linear time algorithm to achieve this bound.