Proof of Theorem 4, p. 53 — if every n₁-set has s independent vertices, then χ(G) ≤ n/s + n₁ (greedy colouring)
ProvedBollobasChromatic.Main.colorable_of_forall_indepchromatic-numbergraph-coloringgraph-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a graph on and let and be integers such that every set of vertices of contains independent vertices. Then
Colouring by repeatedly removing independent -sets until fewer than vertices remain gives this bound; with and from the proof of Theorem 4 it gives the upper bound .
Formalization Note The page's bound is real; since is an integer the two forms are equivalent. The hypothesis is implicit on the page (); for the claim is false.
Preamble
import Mathlib import Definitions.Def_BollobasChromatic_Main_Setting
Formal statement
namespace BollobasChromatic.Main
open Filter Topology Asymptotics
theorem colorable_of_forall_indep (n : ℕ) (G : SimpleGraph (Fin n)) (s n1 : ℕ) (hs : 1 ≤ s)
(hind : ∀ S : Finset (Fin n), S.card = n1 → ∃ T ⊆ S, G.IsNIndepSet s T) :
G.Colorable (n / s + n1) := by sorry
end BollobasChromatic.Main
Source
Bollobás, The chromatic number of random graphs, Combinatorica 8 (1988), p. 53, proof of Theorem 4 (greedy colouring paragraph)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.