MINIMUM COLOR SUM

• INSTANCE: Graph $G=\left(V,E\right)$.
• SOLUTION: A coloring of G, i.e., a partition of V into disjoint sets $V_1,V_2,\ldots,V_k$ such that each $V_i$ is an independent set for G.
• MEASURE: The sum of the coloring, i.e. $\sum_{1\le i\le k}\sum_{v\in V_i} i$.

  
  

• 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 $k_1\le\ldots\le k_{\vert V\vert}$, and i is changed to $k_i$ in the objective function, is not approximable within $\vert V\vert^{1-\varepsilon }$ even for split, chordal, permutation and comparability graphs. For bipartite and interval graphs, the problem is approximable within $\vert V\vert^{0.5}$ but not within $\vert V\vert^{0.5-\varepsilon }$ [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 $V_i$ such that each $V_i$ is an independent set. The objective is to minimize $\sum_{v \in V} f(v)$, where f(v) is the largest k such that v is assigned to $V_k$. In the non-preemptive variant, a vertex v must be assigned to contiguous sets $V_{i+1}, V_{i+2}, \ldots, V_{i + x(v)}$. This variant is approximable within $O(\log n)$ on perfect graphs, 2.796 on bipartite graphs, and $\Delta+1$ 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 $16 \rho$ on graphs where MAXIMUM INDEPENDENT SET is approximable within $\rho$, within 2 on line graphs, 1.5 on bipartite graphs, and $(\Delta+2)/3$ on bounded-degree graphs [58], and admits a PTAS on trees [228] and on partial k-trees and planar graphs [226].