AFTD Auto-Formalizing Theoretical Domains

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 : ℕ∞)
See it in the graphDiscuss this resultChallenge it