A short proof of Brooks' Theorem for vertex arboricity. Issue 1 (2nd January 2020)

• Record Type: Journal Article
• Authors: Bickle, Allan
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 17:Issue 1(2020)
• Page Start: 419
• Page End: 421
• Publication Date: 2020-01-02
• Subjects: Brooks' Theorem -- Vertex arboricity -- Degeneracy -- Vertex coloring
• DOI: 10.1016/j.akcej.2019.03.005
• Languages: English
• ISSNs: 0972-8600

Abstract

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.