Sum coloring

In graph theory, a sum coloring of a graph is a labeling of its vertices by positive integers, with no two adjacent vertices having equal labels, that minimizes the sum of the labels.

[1] Chromatic sums and sum coloring were introduced by Supowit in 1987 using non-graph-theoretic terminology,[2] and first studied in graph theoretic terms by Ewa Kubicka (independently of Supowit) in her 1989 doctoral thesis.

[3] Obtaining the chromatic sum may require using more distinct labels than the chromatic number of the graph, and even when the chromatic number of a graph is bounded, the number of distinct labels needed to obtain the optimal chromatic sum may be arbitrarily large.

[4] Computing the chromatic sum is NP-hard.

[7][8] The interval graph case remains NP-hard.

Sum coloring of a tree. The sum of the labels is 11, smaller than could be achieved using only two labels.