Weighted Coloring: Further Complexity and Approximability Results

Given a vertex-weighted graph G = (V,E;w), w(v) ≥ 0 for any v ∈ V, we consider a weighted version of the coloring problem which consists in finding a partition ${\mathcal S}=(S_{1}...,S_{k})$of the vertex set V of G into stable sets and minimizing ∑i=1kw(Si) where the weight of S is defined as max{w(v) : v ∈ S}. In this paper, we keep on with the investigation of the complexity and the approximability of this problem by mainly answering one of the questions raised by D. J. Guan and X. Zhu (”A Coloring Problem for Weighted Graphs”, Inf. Process. Lett. 61(2):77-81 1997).