Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648807 | Discrete Mathematics | 2011 | 7 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Kishore Yadav, Satish Varagani, Kishore Kothapalli, V.Ch. Venkaiah,