PreprintCC BY 4.0arXiv
An elementary proof of a tight Δ+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 η(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 η(G) ≤ Δ(G) + 1. This argument yields a (Δ(G) + 1)-additive-coloring in polynomial time and improves upon the current best bound of η(G) ≤ Δ(G)2 − Δ(G) + 1, valid for Δ(G) ≥ 2, from Akbari, Ghanbari, Manaviyat, and Zare.
Related
BibTeX
@misc{koutsoutis2026elementary,
title = {{An elementary proof of a tight $Δ+1$ bound for the additive chromatic number}},
author = {Alex Koutsoutis and Joseph Koutsoutis},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.30174},
eprint = {2610.30174},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.30174},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - An elementary proof of a tight Δ+1 bound for the additive chromatic number
AU - Alex Koutsoutis
AU - Joseph Koutsoutis
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.30174
UR - https://arxiv.org/abs/2610.30174
AB - 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 η(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 η(G) ≤ Δ(G) + 1. This argument yields a (Δ(G) + 1)-additive-coloring in polynomial time and improves upon the current best bound of η(G) ≤ Δ(G)^2 − Δ(G) + 1, valid for Δ(G) ≥ 2, from Akbari, Ghanbari, Manaviyat, and Zare.
ER -