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

Abstract

An additive coloring assigns positive integer labels to the vertices of a graph so that adjacent vertices have different sums of their neighbors' labels. The additive chromatic number $\eta (G)$ is the least $k$ for which labels from $[k]$ suffice. We give an elementary orientation argument proving that every finite simple graph $G$ satisfies $\eta (G)\le \Delta (G)+1$. This argument yields a $(\Delta (G)+1)$-additive-coloring in polynomial time and improves upon the current best bound of $\eta (G)\le \Delta (G{)}^2-\Delta (G)+1$, valid for $\Delta (G)\ge 2$, from Akbari, Ghanbari, Manaviyat, and Zare.