Vertex arboricity and maximum degree Original Research Article

The vertex arboricity of graph G is the minimum number of colors that can be used to color the vertices of G so that each color class induces an acylic subraph of cyclic subgraph of G. We prove results such as this: if a connected graph G is neither a cycle nor a clique, then there is a coloring of V(G) with at most ⌈ Δ (G)/2 ⌉ colors, such that each color class induces a forest and one of those induced forests is a maximum induced forest in G. This improves prior results of Brooks (1941). Kronk and Mitchem (1974/75), and Lovász (1966), and it is analogus to a result of Catlin (1976, 1979) on the chromatic number that improves Brooksʹ theorem.