An elementary proof of a tight $Δ+1$ bound for the additive chromatic number

Introduction

All graphs in this paper are simple and finite. Let $G$ be a graph and $f : V(G) \to\mathbb{N}^{*}$ a vertex coloring of $G$. For a vertex $v \in V(G)$, write

If $S_f(u) \ne S_f(v)$ for every edge $\{u,v\} \in E(G)$, then $f$ is an additive coloring of $G$. The additive chromatic number of $G$, denoted by $\eta(G)$, is the least positive integer $k$ for which $G$ admits an additive coloring with labels in $[k]$.

Additive colorings were introduced by Czerwiński, Grytczuk, and Żelazny [3] using the terms lucky labeling and lucky number for additive coloring and additive chromatic number, respectively.

For general graphs, the best known upper bound on $\eta(G)$ in terms of the maximum degree has been quadratic. Akbari, Ghanbari, Manaviyat, and Zare [1] studied the list version of the problem: the lucky choice number $\eta_{\ell}(G)$ is the least $k$ such that, whenever each vertex $v$ is given a set $L(v)$ of $k$ positive integers, there is an additive coloring $f$ with $f(v) \in L(v)$ for every $v$. They proved that $\eta_{\ell}(G) \le\Delta(G)^2 - \Delta(G) + 1$ for $\Delta(G) \ge2$. Since $\eta(G) \le\eta_{\ell}(G)$, this gives

Severín [5] describes this as the best known upper bound on $\eta(G)$ in terms of $\Delta(G)$, and we are not aware of any later improvement that holds for all graphs.

Gossett [4] proved an additive analogue of the Alon–Tarsi theorem [2]: if some orientation of $G$ satisfies an Alon–Tarsi-type condition, then lists whose sizes exceed the outdegrees by one suffice. He conjectured that every graph has such an orientation; this conjecture would imply $\eta_{\ell}(G) \le\Delta(G) + 1$ for every graph $G$.

We improve (1) to $\eta(G) \le\Delta(G) + 1$, which is tight since $\eta(K_{\Delta+1}) = \Delta+ 1$. In fact, we prove a stronger statement: for any choice of positive integers $\{a_v\}_{v \in V(G)}$, there is an additive coloring $f$ with $f(v) \in\{a_v, a_v + 1, \ldots, a_v + d(v)\}$ for every vertex $v$. Moreover, this coloring is obtainable in polynomial time.

Proof of the upper bound

The proofs of the previous upper bounds rely on algebraic tools such as the Combinatorial Nullstellensatz and Alon–Tarsi-type orientation criteria [1, 3, 4]. Our proof is elementary and constructive.

Proof. For an orientation $D$ of $G$, put

Choose $D$ minimizing $\Phi$ among the finitely many orientations. If $(u,v)$ is an arc in $D$ and $D'$ is the orientation with this one arc reversed, then we compute

For $w\ne u,v$, using similar computation to above, if $\{u,w\}\in E(G)$,

and if $\{w,v\}\in E(G)$,

Combining (2), (3), and (4) and writing $f=f_D$ gives

By minimality of $D$, $S_f(v)\ge S_f(u)+1$ on every arc $(u,v)$. □

This translates to a $(\Delta(G)+1)$-additive-coloring in polynomial time:

Proof. Each reversal decreases $\Phi$ by exactly 1 by (5). Through the process, we maintain $1\le f_D(v)\le\Delta(G)+1$. Hence

Tool and computational resource disclosure

The proofs in this paper were assisted by ChatGPT-6 Astra and Claude Opus 5.5. We subsequently reviewed and refined the ideas, wrote them as shown above, and take full responsibility for the content of this paper.