pipette
ESEspañol

An elementary proof of a tight bound for the additive chromatic number

Alex Koutsoutis, Joseph Koutsoutis

Preprint

In the authors' words

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 is the least for which labels from suffice. We give an elementary orientation argument proving that every finite simple graph satisfies . This argument yields a -additive-coloring in polynomial time and improves upon the current best bound of , valid for , from Akbari, Ghanbari, Manaviyat, and Zare.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 23. arXiv. Preprint, not yet peer-reviewed.