Recognition: unknown
Brooks' Vertex-Colouring Theorem in Linear Time
read the original abstract
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 vertex-colouring with $\Delta$ colours, unless $G$ is a complete graph or an odd cycle, in which case $\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.
This paper has not been read by Pith yet.
Forward citations
Cited by 2 Pith papers
-
Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota's Basis Conjecture
First poly-time algorithms for matroid-intersection coloring achieve a 2-approximation for two matroids and (k^2-k) approximation for k matroids, plus an FPRAS for asymptotic Rota's Basis Conjecture.
-
Beyond Brooks: $(\Delta-1)$-Coloring in Semi-Streaming
A one-pass semi-streaming algorithm computes (Δ-1)-colorings for large-degree graphs without Δ-cliques, together with an Ω(n(k+1)) space lower bound for (Δ-k)-coloring when k is smaller.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.