A short proof of Brooks’ Theorem for vertex arboricity
Allan Bickle · AKCE International Journal of Graphs and Combinatorics · 2019
The vertex-arboricity aG of a graph G is the minimum number of subsets that the vertices of G can be partitioned so that the subgraph induced by each set of vertices is a forest. Kronk and Mitchem proved a generalization of Brooks’ Theorem for vertex arboricity, aG=1+12△G if and only if G is a cycle or a complete graph of odd order. We provide a short proof of this result using degeneracy.