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. Chromatic sums and sum coloring were introduced by Supowit in 1987 using non-graph-theoretic terminology, and first studied in graph theoretic terms by

Ewa Kubicka Ewa Maria Kubicka is a Polish mathematician interested in graph theory and actuarial science. She is known for introducing the concept of the chromatic sum of a graph, the minimum possible sum when the vertices are labeled by natural numbers with ...

(independently of Supowit) in her 1989 doctoral thesis. 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. Computing the chromatic sum is

NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

. However it may be computed in

linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

for trees and pseudotrees, and in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

for outerplanar graphs. There is a constant-factor

approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...

for interval graphs and for

bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...

s. The interval graph case remains NP-hard. It is the case arising in Supowit's original application in VLSI design, and also has applications in scheduling.

References

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