Sum coloring

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

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]

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]

References

1. Małafiejski, Michał (2004), "Sum coloring of graphs", in Kubale, Marek (ed.), Graph Colorings, Contemporary Mathematics, vol. 352, Providence, RI: American Mathematical Society, pp. 55–65, doi:10.1090/conm/352/06372, ISBN 9780821834589, MR 2076989
2. Supowit, K. J. (1987), "Finding a maximum planar subset of a set of nets in a channel", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 6 (1): 93–94, doi:10.1109/tcad.1987.1270250, S2CID 14949711
3. Kubicka, Ewa Maria (1989), The chromatic sum and efficient tree algorithms, Ph.D. thesis, Western Michigan University, MR 2637573
4. Erdős, Paul; Kubicka, Ewa; Schwenk, Allen J. (1990), "Graphs that require many colors to achieve their chromatic sum", Proceedings of the Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1989), Congressus Numerantium, 71: 17–28, MR 1041612
5. Kubicka, Ewa; Schwenk, Allen J. (1989), "An introduction to chromatic sums", Proceedings of the 17th ACM Computer Science Conference (CSC '89), New York, NY, USA: ACM, pp. 39–45, doi:10.1145/75427.75430, ISBN 978-0-89791-299-0, S2CID 28544302
6. Kubicka, Ewa M. (2005), "Polynomial algorithm for finding chromatic sum for unicyclic and outerplanar graphs", Ars Combinatoria, 76: 193–201, MR 2152758
7. Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas (2001), "Minimizing average completion of dedicated tasks and interval graphs", Approximation, randomization, and combinatorial optimization (Berkeley, CA, 2001), Lecture Notes in Computer Science, vol. 2129, Berlin: Springer, pp. 114–126, doi:10.1007/3-540-44666-4_15, ISBN 978-3-540-42470-3, MR 1910356
8. Giaro, Krzysztof; Janczewski, Robert; Kubale, Marek; Małafiejski, Michał (2002), "A 27/26-approximation algorithm for the chromatic sum coloring of bipartite graphs", Approximation algorithms for combinatorial optimization, Lecture Notes in Computer Science, vol. 2462, Berlin: Springer, pp. 135–145, doi:10.1007/3-540-45753-4_13, ISBN 978-3-540-44186-1, MR 2091822
9. Marx, Dániel (2005), "A short proof of the NP-completeness of minimum sum interval coloring", Operations Research Letters, 33 (4): 382–384, CiteSeerX 10.1.1.5.2707, doi:10.1016/j.orl.2004.07.006, MR 2127409