| Article ID: | iaor2006920 |
| Country: | Netherlands |
| Volume: | 33 |
| Issue: | 4 |
| Start Page Number: | 382 |
| End Page Number: | 384 |
| Publication Date: | Jul 2005 |
| Journal: | Operations Research Letters |
| Authors: | Marx Dniel |
| Keywords: | graphs |
In the minimum sum coloring problem we have to assign positive integers to the vertices of a graph in such a way that neighbors receive different numbers and the sum of the numbers is minimized. Szkalicki has shown that minimum sum coloring is NP-hard for interval graphs. Here we present a simpler proof of this result.