thumb|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.{{r|scg}} Chromatic sums and sum coloring were introduced by Supowit in 1987 using non-graph-theoretic terminology,{{r|sup}} and first studied in graph theoretic terms by Ewa Kubicka (independently of Supowit) in her 1989 doctoral thesis.{{r|k89}}
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.{{r|eks}}
Computing the chromatic sum is NP-hard. However it may be computed in linear time for trees and pseudotrees,{{r|intro|ucop}} and in polynomial time for outerplanar graphs.{{r|ucop}} There is a constant-factor approximation algorithm for interval graphs and for bipartite graphs.{{r|hks|gjkm}} The interval graph case remains NP-hard.{{r|marx}} It is the case arising in Supowit's original application in VLSI design, and also has applications in scheduling.{{r|hks}}
==References== <references>
<ref name=eks>{{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}}</ref>
<ref name=gjkm>{{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 }}</ref>
<ref name=hks>{{citation | last1 = Halldórsson | first1 = Magnús M. | last2 = Kortsarz | first2 = Guy | last3 = Shachnai | first3 = Hadas | author3-link = Hadas Shachnai | 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 }}</ref>
<ref name=intro>{{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| s2cid = 28544302 | doi-access = free }}</ref>
<ref name=k89>{{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}}</ref>
<ref name=marx>{{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 }}</ref>
<ref name=scg>{{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 | doi-access = free }}</ref>
<ref name=sup>{{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| bibcode = 1987ITCAD...6...93S | s2cid = 14949711 }}</ref>
<ref name=ucop>{{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}}</ref>
</references>
Category:Graph coloring Category:NP-complete problems