Additive Coloring

An additive coloring, also called a lucky labeling, of a finite simple graph assigns positive integers to its vertices so that adjacent vertices have different sums of the labels of their neighbors. The additive chromatic number is the least for which labels from 1 through suffice (Koutsoutis and Koutsoutis 2026).

Koutsoutis and Koutsoutis (2026) proved that , where is the maximum degree. This is sharp since for the complete graph . More strongly, for arbitrary positive integers , the label at each vertex can be chosen from , where is its vertex degree. This proves the bound for consecutive integer lists, not an arbitrary-list version. Koutsoutis and Koutsoutis (2026) acknowledge AI assistance with the proof.