Brooks' Vertex-Colouring Theorem in Linear Time

Bradley Baetz, David R. Wood

Brooks' Theorem [R. L. Brooks, On Colouring the Nodes of a Network, Proc. Cambridge Philos. Soc.} 37:194-197, 1941] states that every graph $G$ with maximum degree $\Delta$, has a verte…