simple_graph_is_choosable
def
A 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 exists a proper coloring choosing a color from each vertex's list.
Statement
def simple_graph_is_choosable {V : Type*} (G : SimpleGraph V) (k : ℕ) : Prop
- 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_multiple_choosableA simple graph G is (a:b)-choosable if for every assignment L of a-element color lists (from ℕ) to the vertices of G, there exists an…
- Used by 1
- simple_graph_choice_numberThe 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…
Read back from the Lean
Given a simple graph G on a type V and a natural number k, simple_graph_is_choosable G k asserts that G is (k, 1)-multiple choosable: for every assignment L : V → Finset ℕ of lists of colors such that (L v).card = k for every vertex v, there exists a choice function φ : V → Finset ℕ such that for every vertex v, φ v ⊆ L v and (φ v).card = 1, and for every pair of adjacent vertices u, v in G, φ u and φ v are disjoint.
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
/-- A simple graph is k-choosable if it is (k:1)-choosable. -/ def simple_graph_is_choosable {V : Type*} (G : SimpleGraph V) (k : ℕ) : Prop := simple_graph_is_multiple_choosable G k 1