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 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
- On Chromatic Sums
and Distributed Resource Allocation, 1998
A. Bar-Noy, N. Bellare, M. Halldórsson, H. Shachnai and T. Tamir
-
A Matched Approximation Bound for the Sum of a Greedy Coloring, 1999
A. Bar-Noy, M. Halldórsson and G. Kortsarz
-
The minimum color-sum of bipartite graphs, 1998
A. Bar-Noy and G. Kortsarz
- A
27/26-Approximation Algorithm for the Chromatic Sum Coloring of
Bipartite Graphs
K. Giaro, R. Janczewski, M. Kubale and M. Malafiejski
-
Edge-chromatic sum of trees and bounded cyclicity graphs, 2000
K. Giaro and M. Kubale
-
Chromatic sum and Mehrabadi's Conjecture
H. Hajiabolhassan
-
Minimal
coloring and strength of graphs, 2000
H. Hajiabolhassan, M. L. Mehrabadi and
R. Tusserkani
- Coloring of Trees with
Minimum Sum of Colors, 1999
T. Jiang and D. B. West
-
Sum Coloring Interval and k-Claw Free Graphs with Application to Scheduling Dependent Jobs
M. Halldórsson, G. Kortsarz and H. Shachnai
-
The
chromatic sum of a graph: history and recent developments, 2003
E. Kubicka
-
An introduction to chromatic sums, 1989
E. Kubicka and A.J. Schwenk
-
The complexity of the chromatic sum problem on cubic planar graphs and regular graphs, 2001
M. Malafiejski
(The link is broken, the paper is no longer available online.)
-
A short proof of the NP-completeness of minimum sum interval coloring, 2003
D. Marx
-
The complexity of chromatic strength and chromatic edge strength, 2004
D. Marx
-
Complexity results for minimum sum edge coloring, 2004
D. Marx
-
On
the Sum Coloring Problem on Interval Graphs, 1999
S. Nicoloso, M. Sarrafzadeh and X. Song
- On Sum
Coloring of Graphs, 2003
M.R. Salavatipour
-
Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is NP-Complete, 1999
T. Szkaliczki
Minimum sum multicoloring
- Sum
Multicoloring of Graphs, 2000
A. Bar-Noy, M. Halldórsson,
G. Kortsarz, R. Salman and H. Shachnai
-
Tools
for Multicoloring with Applications to Planar Graphs and Partial
k-Trees, 2002
M. Halldórsson and G. Kortsarz
- Multicoloring Trees, 2003
M. Halldórsson, G. Kortsarz, A. Proskurowski, R. Salman, H. Shachnai and J.A. Telle
-
Sum Coloring Interval and k-Claw Free Graphs with Application to Scheduling Dependent Jobs
M. Halldórsson, G. Kortsarz and H. Shachnai
- Resource-Constrained
Scheduling and Graph Multicoloring with Min-sum Objectives, 2000
M.M. Halldórsson, G. Kortsarz and H. Shachnai
-
Data Migration to Minimize the Average Completion Time, 2003
Y.A. Kim
- Sum-multicoloring
on Paths, 2003
A. Kovács
- Polynomial
Time Preemptive Sum-Multicoloring on Paths, 2005
A. Kovács
-
The complexity of tree multicolorings, 2002
D. Marx
-
Minimum sum multicoloring on the edges of trees, 2003
D. Marx
Maintained by Dániel Marx.
Last updated:
September 1, 2008
Back to my homepage