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. The minimum sum that can be achieved is called the chromatic sum of the graph.^[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]

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

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. However it may be computed in linear time for trees and pseudotrees,^[5][6] and in polynomial time for outerplanar graphs.^[6] There is a constant-factor approximation algorithm for interval graphs and for bipartite graphs.^[7][8] The interval graph case remains NP-hard.^[9] It is the case arising in Supowit's original application in VLSI design, and also has applications in scheduling.^[7]