A short proof of Brooks' Theorem for vertex arboricity. Issue 1 (2nd January 2020) - Bickle, Allan
Abstract: The vertex-arboricity a G 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, a G = 1 + 1 2 △ 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.