simple_graph_is_seal_free_partition
def
A vertex map p : V → Fin q is a seal-free block partition for an edge colouring γ of a graph G when (i) every block {v | p v = i} induces a connected subgraph of G (this also forces every block to be nonempty), and (ii) for every colour γ e of an edge and every nonempty proper set T of block labels, some edge of colour γ e crosses from T to its complement.
Statement
def simple_graph_is_seal_free_partition {V α : Type*} (G : SimpleGraph V) (γ : G.edgeSet → α) (q : ℕ) (p : V → Fin q) : Prop
- Source
- step towards quadripartite_minimum_coloring_max_wild_number_eq
- Verified
- 31 Oct 2026
- Axioms
- none listed
- Used by 2
- simple_graph_is_seal_free_partition_one_blockIf G is a connected graph with edge colouring γ, then the one-block vertex map (everything ↦ 0) is a seal-free partition.
- quadripartite_exists_wild_number_eq_of_upper_exclusionIf every proper 3n-edge-colouring of K_{n,n,n,n} has wild number at most 2n + 1, and some colouring has no colour-connecting set of at…
Lean source view module on GitHub
/-- A partition of the vertices into connected blocks such that every edge colour crosses every proper nonempty cut of blocks. -/ def simple_graph_is_seal_free_partition {V α : Type*} (G : SimpleGraph V) (γ : G.edgeSet → α) (q : ℕ) (p : V → Fin q) : Prop := (∀ i : Fin q, (SimpleGraph.induce {v : V | p v = i} G).Connected) ∧ ∀ (e : G.edgeSet) (T : Finset (Fin q)), T.Nonempty → T ≠ Finset.univ → ∃ (u v : V) (h : G.Adj u v), p u ∈ T ∧ p v ∉ T ∧ γ ⟨s(u, v), by simpa using h⟩ = γ e