is_admissible_list_assignment
def
A 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 cardinality m and the lists assigned to distinct nonadjacent vertices are disjoint.
Statement
def is_admissible_list_assignment {V : Type*} (G : SimpleGraph V) (m : ℕ) (L : V → Finset ℕ) : Prop
- Defined in
- arXiv:2611.07924, Section 1
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Used by 1
- graph_min_color_setsFor 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…
Read back from the Lean
For a simple graph G on a vertex type V, a natural number m, and a list assignment L : V → Finset ℕ, is_admissible_list_assignment G m L asserts that:
1. For every vertex v : V, the size of L v is m.
2. For all vertices u, v : V, if u and v are adjacent in the complement graph Gᶜ (that is, u ≠ v and u is not adjacent to v in G), then the sets L u and L 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 list assignment L of m-element subsets of ℕ on a simple graph G is admissible if L(u) and L(v) are disjoint whenever u and v are distinct nonadjacent vertices. -/ def is_admissible_list_assignment {V : Type*} (G : SimpleGraph V) (m : ℕ) (L : V → Finset ℕ) : Prop := (∀ v : V, (L v).card = m) ∧ (∀ u v : V, Gᶜ.Adj u v → Disjoint (L u) (L v))