IsStronglyChromaticChoosable
def
A graph G is strongly ℓ-chromatic-choosable if χ(G) = ℓ and every (ℓ-1)-assignment L for which G is not L-colorable has all lists equal; equivalently, every (ℓ-1)-assignment whose lists are not all identical admits a proper coloring c with c(v) ∈ L(v). Colours are natural numbers, which loses no generality since the lists are finite.
Statement
def IsStronglyChromaticChoosable {V : Type*} (G : SimpleGraph V) (ℓ : ℕ) : Prop
- Defined in
- arXiv:2610.14241 (Restricting odd antiholes in critical graphs via list coloring), Sec. 2, before Conjecture 9 (definition of strong ℓ-chromatic-choosability)
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Used by 1
- cycle_five_compl_strongly_chromatic_choosableThe case ℓ = 3 of Conjecture 9: the complement of C_5 (itself a 5-cycle) is strongly 3-chromatic-choosable: χ = 3 and it is colorable from…
Lean source view module on GitHub
/-- `G` is strongly `ℓ`-chromatic-choosable: `χ(G) = ℓ`, and every assignment of lists of size `ℓ - 1` (colours in `ℕ`) under which `G` is not list-colourable gives every vertex the same list. -/ def IsStronglyChromaticChoosable {V : Type*} (G : SimpleGraph V) (ℓ : ℕ) : Prop := G.chromaticNumber = ℓ ∧ ∀ L : V → Finset ℕ, (∀ v, (L v).card = ℓ - 1) → (∃ u v, L u ≠ L v) → ∃ c : V → ℕ, (∀ v, c v ∈ L v) ∧ ∀ u v, G.Adj u v → c u ≠ c v