Brooks' Vertex-Colouring Theorem in Linear Time

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 $\mathrm{\Delta }$, has a vertex-colouring with $\mathrm{\Delta }$ colours, unless $G$ is a complete graph or an odd cycle, in which case $\mathrm{\Delta }+1$ colours are required. Lov'asz [L. Lov'asz, Three short proofs in graph theory, J. Combin. Theory Ser. 19:269-271, 1975] gives an algorithmic proof of Brooks’ Theorem. Unfortunately this proof is missing important details and it is thus unclear whether it leads to a linear time algorithm. In this paper we give a complete description of the proof of Lov'asz, and we derive a linear time algorithm for determining the vertex-colouring guaranteed by Brooks’ Theorem.