is_additive_coloring
def
An additive coloring of a finite simple graph G is a vertex labeling f : V → ℕ with positive integers such that for every edge {u, v}, the sum of labels in the neighborhood of u differs from the sum of labels in the neighborhood of v.
Statement
def is_additive_coloring {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (f : V → ℕ) : Prop
- Defined in
- arXiv:2610.30174, Section 1
- Verified
- 23 Oct 2026
- Axioms
- none listed
- Used by 2
- is_additive_coloring_le_iffA vertex labeling f on a finite graph G is an additive coloring bounded by k if and only if 1 ≤ f(v) ≤ k for all vertices v and adjacent…
- op_494_additive_chromatic_bipartite_maxDegreeLet G be a finite connected bipartite simple graph with maximum degree at least 2. Then there exists a vertex labeling f : V → ℕ such that…
Read back from the Lean
Given a finite type V, a simple graph G on V with decidable adjacency, and a labeling f : V → ℕ, is_additive_coloring G f asserts that:
1. For every vertex v : V, 0 < f v (i.e., every vertex receives a positive natural number); and
2. For all vertices u, v : V, if u and v are adjacent in G, then the sum of f w over all neighbors w of u is not equal to the sum of f w over all neighbors w of v.
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
/-- An additive coloring of a graph assigns positive integers to vertices such that adjacent vertices have distinct neighborhood sums. -/ def is_additive_coloring {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (f : V → ℕ) : Prop := (∀ v, 0 < f v) ∧ ∀ ⦃u v : V⦄, G.Adj u v → ∑ w ∈ G.neighborFinset u, f w ≠ ∑ w ∈ G.neighborFinset v, f w