2014/01/30 by Bradley Baetz, David R. Wood, Baetz, Bradley +1
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1401.8023
openalex publication_date 2014/01/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Δ, has a vertex-colouring with Δ colours, unless G is a complete graph or an odd cycle, in which case Δ+1 colours are required. Lovász [L. Lovász, 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ász, and we derive a linear time algorithm for determining the vertex-colouring guaranteed by Brooks' Theorem.