simple_graph_choice_number
def
The choice number (or list chromatic number) ch(G) of a simple graph G is the infimum over all natural numbers k such that G is k-choosable, as an element of ℕ∞.
Statement
noncomputable def simple_graph_choice_number {V : Type*} (G : SimpleGraph V) : ℕ∞
- Defined in
- arXiv:2611.03151, Section 1; Erdős, Rubin, Taylor (1979)
- Verified
- 05 Nov 2026
- Axioms
- none listed
- Built on 1
- simple_graph_is_choosableA simple graph G is k-choosable if it is (k:1)-choosable, i.e., for every assignment of k-element color lists to the vertices, there…
Read back from the Lean
Given a type V and a simple graph G on V, simple_graph_choice_number G is defined as the infimum (in ℕ∞, the extended natural numbers) of all natural numbers k such that G is choosable (list-colorable) with list size k. If no such k exists, the infimum over the empty set evaluates to ⊤ (infinity).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The choice number (list chromatic number) of a simple graph as an extended natural number. -/ noncomputable def simple_graph_choice_number {V : Type*} (G : SimpleGraph V) : ℕ∞ := ⨅ k ∈ {n : ℕ | simple_graph_is_choosable G n}, (k : ℕ∞)