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 S=(S1,…,Sk) of the vertex set of G into stable sets and minimizing where the weight of S is defined as . In this paper, we continue the investigation of the complexity and the approximability of this problem by answering some of the questions raised by Guan and Zhu [D.J. Guan, X. Zhu, A coloring problem for weighted graphs, Inform. Process. Lett. 61 (2) (1997) 77–81].