Generalization of MINIMUM COLOR SUM where the input is extended by
positive coloring costs
,
and i is
changed to ki in the objective function, is not approximable within
even for split, chordal, permutation and
comparability graphs, but for bipartite and interval graphs the problem
is approximable within |V|0.5, but not within
[255].