simple_graph_coloring_is_frozen
def
A proper colouring with colours [k] is frozen if for every vertex x and colour i, x or some neighbour of x has colour i.
Statement
def simple_graph_coloring_is_frozen {W : Type*} {H : SimpleGraph W} {k : ℕ} (C : H.Coloring (Fin k)) : Prop
- Defined in
- arXiv:2610.27527 (Frozen colorings and recolorability of blowups), Sec. 1, definition of a frozen colouring
- Verified
- 21 Oct 2026
- Axioms
- none listed
- Used by 1
- simple_graph_clique_blowup_coloring_frozen_iffFor a clique blowup G(w) with positive weights, a proper colouring α of G(w) is frozen iff for every colour i the set I_i(α) of vertices v…
Lean source view module on GitHub
/-- A proper k-colouring is frozen if every vertex sees every colour in its closed neighbourhood, so no single vertex can be recoloured. -/ def simple_graph_coloring_is_frozen {W : Type*} {H : SimpleGraph W} {k : ℕ} (C : H.Coloring (Fin k)) : Prop := ∀ (x : W) (i : Fin k), C x = i ∨ ∃ y, H.Adj x y ∧ C y = i