Critical Graphs for Acyclic Colorings
David Monty Berman · Canadian Mathematical Bulletin · 1978
The concept of acyclic colorings of graphs, introduced by Grunbaum [2], is a generalization of point-arboricity. An acyclic coloring of a graph is a proper coloring of its points such that there is no two-colored cycle. We denote by a(G), the acyclic chromatic number of a graph G, the minimum number of colors for an acyclic coloring of G. We call G k-critical if a(G) = fc but a(G′) for any proper subgraph G′. For all notation and terminology not defined here, see Harary [3].