BROOKS GRAPH-COLORING THEOREM AND THE INDEPENDENCE NUMBER

Let h denote the maximum degree of a connected graph H, and let χ(H) denote its chromatic, number. Brooks' Theorem asserts that if h ≥ 3, then χ(H) ≤ h, unless H is the complete graph Kh+1. We show that when H is not Kh+1, there is an h-coloring of H in which a maximum independent set is monochromatic. We characterize those graphs H having an h-coloring in which some color class consists of vertices of degree h in H. Again, without any loss of generality, this color class may be assumed to be maximum with respect to the condition that its vertices have degree h. © 1979.