Chromatic sum and minimum sum multicoloring

In the minimum sum coloring problem we have to assign a color (positive integer) to each vertex of the graph such that the sum of these integers is minimal. The smallest sum that can be achieved is the chromatic sum of the graph. The concept was introduced by E. Kubicka in 1989.

In the minimum sum multicoloring problem each vertex has a demand which tells us how many colors have to be assigned to the vertex (minimum sum coloring is the special case where every demand is 1). As usual, the colors have to be assigned in such a way that a color cannot appear on two neighboring vertices. The optimization goal is the following: the finish time of a vertex is defined to be the largest color assigned to it, our goal is to minimize the sum of these finish times. The problem definition might seem a bit artificial, but it is motivated by applications in scheduling.

I have compiled a small collection of links to online papers on chromatic sum, minimum sum coloring and minimum sum multicoloring. If you find that a relevant paper is missing or a link is wrong, then please mail me.

The restricted access sign means that full text can be accessed only if you or your institution is subscribed to the online service.

Chromatic sum, minimum sum coloring

Minimum sum multicoloring

Maintained by Dániel Marx.
Last updated: September 1, 2008
Back to my homepage