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]
References
Małafiejski, Michał (2004), "Sum coloring of graphs", in Kubale, Marek (ed.), Graph Colorings, Contemporary Mathematics, 352, Providence, RI: American Mathematical Society, pp. 55–65, doi:10.1090/conm/352/06372, ISBN 9780821834589, MR 2076989
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
Kubicka, Ewa Maria (1989), The chromatic sum and efficient tree algorithms, Ph.D. thesis, Western Michigan University, MR 2637573
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
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
Kubicka, Ewa M. (2005), "Polynomial algorithm for finding chromatic sum for unicyclic and outerplanar graphs", Ars Combinatoria, 76: 193–201, MR 2152758
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, 2129, Berlin: Springer, pp. 114–126, doi:10.1007/3-540-44666-4_15, ISBN 978-3-540-42470-3, MR 1910356
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, 2462, Berlin: Springer, pp. 135–145, doi:10.1007/3-540-45753-4_13, ISBN 978-3-540-44186-1, MR 2091822
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
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
