A unified proof of Brooks' theorem and Catlin's theorem

Brooks' theorem is a fundamental result in the theory of graph coloring. Catlin proved the following strengthening of Brooks' theorem: Let d be an integer at least 3, and let G be a graph with maximum degree d. If G does not contain Kd+1 as a subgraph, then G has a d-coloring in which one color class has size alpha(G). Here alpha(G) denotes the independence number of G. We give a unified proof of Brooks' theorem and Catlin's theorem. (C) 2014 Elsevier B.V. All rights reserved.