is_strong_odd_coloring
A vertex coloring f : V → κ of a finite simple graph G is a strong odd coloring if it is proper and, for every vertex v and every color c, the number of neighbors of v colored c is either zero or odd.
Statement
def is_strong_odd_coloring {V κ : Type*} [Fintype V] [DecidableEq κ] (G : SimpleGraph V) [DecidableRel G.Adj] (f : V → κ) : Prop
- Defined in
- arXiv:2610.34874
- Verified
- 27 Oct 2026
- Axioms
- none listed
- Used by 3
- strong_odd_coloring_insert_vertexLet g be a colouring of a finite simple graph G which is a strong odd colouring of G - v; if g v avoids the colours of all neighbours of v…
- is_strong_odd_list_colorableA finite simple graph G is strongly odd k-list-colorable if for every assignment L of color lists of size at least k to the vertices from…
- strong_odd_five_coloring_of_list_colorableIf a finite simple graph is strongly odd 5-list-colorable, then it admits an ordinary strong odd 5-coloring.
Read back from the Lean
For a finite type V, a type κ with decidable equality, a simple graph G on V with decidable adjacency, and a vertex-coloring function f : V → κ, is_strong_odd_coloring G f asserts that:
1. f is a proper coloring: for all vertices u, v : V, if u and v are adjacent in G, then f u ≠ f v; and
2. For every vertex v : V and every color c : κ, the set of neighbors of v assigned color c is either empty or has odd cardinality (i.e., every color appearing in the neighborhood of v appears an odd number of times).
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 proper coloring where each color appearing on the neighborhood of any vertex appears an odd number of times. -/ def is_strong_odd_coloring {V κ : Type*} [Fintype V] [DecidableEq κ] (G : SimpleGraph V) [DecidableRel G.Adj] (f : V → κ) : Prop := (∀ {u v : V}, G.Adj u v → f u ≠ f v) ∧ ∀ (v : V) (c : κ), (G.neighborFinset v).filter (fun u => f u = c) = ∅ ∨ Odd ((G.neighborFinset v).filter (fun u => f u = c)).card