AFTD Auto-Formalizing Theoretical Domains

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
See it in the graphDiscuss this resultChallenge it