Next: Vertex Ordering Up: Subgraphs and Supergraphs Previous: MINIMUM CHORDAL GRAPH COMPLETION Index

### MINIMUM COLOR SUM

- INSTANCE: Graph .

- SOLUTION: A coloring of G, i.e., a partition of V into disjoint sets such that each Vi is an independent set for G.

- MEASURE: The sum of the coloring, i.e. .

- Good News: As easy as MAXIMUM INDEPENDENT SET[54], within a constant factor.

- Bad News: As hard as MINIMUM GRAPH COLORING[54,144].

- Comment: The good news hold for any hereditary class of graphs. In particular, perfect graphs are 4-approximable [54]. For bipartite graphs the problem is APX-complete and approximable within 10/9 [55]. Edge graphs are approximable within 2 [54], and so are interval graphs [402]

  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].