Brooks' Theorem for k ≥ 3
ProvedBrooks.colorable_of_max_deg_cliqueFreebrooks-theoremcombinatoricsgraph-theoryvertex-coloring
Brooks' Theorem (). Let be a finite simple graph with maximum degree at most , where . If contains no -clique (-free), then is properly -vertex-colorable:
Preamble
import Mathlib.Combinatorics.SimpleGraph.Coloring.Vertex import Mathlib.Data.Set.Card universe u namespace Brooks
Formal statement
theorem colorable_of_max_deg_cliqueFree
{V : Type u} [Fintype V] (G : SimpleGraph V) {k : ℕ} (hk : 3 ≤ k)
(hdeg : ∀ v : V, (G.neighborSet v).encard ≤ k)
(hnoK : G.CliqueFree (k + 1)) :
G.Colorable k := by sorry
end BrooksSource
R. L. Brooks, On colouring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1941), 194–197; formalized via M. Zając, A short proof of Brooks' theorem, arXiv:1805.11176 (2018).