graph_min_color_sets
For a finite vertex type V, a simple graph G on V, and an integer m, graph_min_color_sets G m is the infimum sInf of the cardinalities (graph_color_sets G L).card over all admissible list assignments L : V → Finset ℕ of list size m on G.
Statement
noncomputable def graph_min_color_sets {V : Type*} [Fintype V] (G : SimpleGraph V) (m : ℕ) : ℕ
- Defined in
- arXiv:2611.07924, Section 1 and Section 2 (Lemma 2.1)
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Built on 2
- is_admissible_list_assignmentA list assignment L assigning to each vertex of a graph G a finite set of natural numbers is admissible for list size m if every list has…
- graph_color_setsGiven a finite vertex type V, a simple graph G on V, and a list assignment L : V → Finset ℕ assigning each vertex a finite set of colors…
Read back from the Lean
Given a finite type $V$, a simple graph $G$ on $V$, and a natural number $m$, graph_min_color_sets G m is the minimum (infimum in $\mathbb{N}$) over all admissible list assignments $L : V \to \mathrm{Finset}\,\mathbb{N}$ of the number of distinct color sets (images $\varphi(V)$) achievable by proper $L$-colorings of $G$.
An admissible list assignment $L$ requires each vertex to have a list of size $m$, and any two distinct vertices that are not adjacent in $G$ to have disjoint lists.
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 minimum number f'(G, m) of distinct color sets used by proper colorings of G from admissible m-element lists. -/ noncomputable def graph_min_color_sets {V : Type*} [Fintype V] (G : SimpleGraph V) (m : ℕ) : ℕ := sInf { N : ℕ | ∃ L : V → Finset ℕ, is_admissible_list_assignment G m L ∧ (graph_color_sets G L).card = N }