Next: MAXIMUM ACHROMATIC NUMBER Up: Covering and Partitioning Previous: MINIMUM GRAPH COLORING   Index

### MINIMUM COLOR SUM

• INSTANCE: Graph .
• SOLUTION: A coloring of G, i.e., a partition of V into disjoint sets such that each is an independent set for G.
• MEASURE: The sum of the coloring, i.e. .

• Good News: As easy as MAXIMUM INDEPENDENT SET[57], within a constant factor.
• Bad News: As hard as MINIMUM GRAPH COLORING[57,156].
• Comment: The good news hold for any hereditary class of graphs. In particular, perfect graphs are approximable within 4 [57]. For bipartite graphs, the problem is APX-complete and approximable within 10/9 [59]. Approximable within 2 on line graphs [57] and on interval graphs [425]. Generalization of MINIMUM COLOR SUM where the input is extended by positive coloring costs , and i is changed to in the objective function, is not approximable within even for split, chordal, permutation and comparability graphs. For bipartite and interval graphs, the problem is approximable within but not within [270]. In a multicoloring generalization, we are given a graph G and an integral color requirement x(v) for each vertex v, and are to assign each vertex to x(v) sets such that each is an independent set. The objective is to minimize , where f(v) is the largest k such that v is assigned to . In the non-preemptive variant, a vertex v must be assigned to contiguous sets . This variant is approximable within on perfect graphs, 2.796 on bipartite graphs, and on bounded degree graphs [58], within O(1) on interval graphs and 12 on line graphs [227], and admits an FPTAS on partial k-trees and a PTAS on planar graphs [226]. The preemptive variant is approximable within on graphs where MAXIMUM INDEPENDENT SET is approximable within , within 2 on line graphs, 1.5 on bipartite graphs, and on bounded-degree graphs [58], and admits a PTAS on trees [228] and on partial k-trees and planar graphs [226].

Next: MAXIMUM ACHROMATIC NUMBER Up: Covering and Partitioning Previous: MINIMUM GRAPH COLORING   Index
Viggo Kann
2000-03-20