I would like to know any results in terms of approximation algorithm about Maximum weight Independent Set problem in coloring graph.
Input: Given a graph G with non-negative vertex weights and valid but not important to be optimal coloring of G.
Task: Find the Maximum weight Independent Set.
Note that this problem is NP-hard (for k>2 where k is the number of coloring) [see here]
in Hochbaum's paper in 1996 "Approximating Covering and Packing Problems: Set Cover, Vertex Cover, Independent Set, and related problems" in Theorem 3.2 he give an (2/k)-approximation algorithm for this problem.
Now, my question is: Is there any new results regarding this problem? Is there any lower bound for this problem? Of course in general for simple graph without coloring to find Independent Set, there is no constant factor unless P=NP. Now, Is it true that we cannot have a constant factor for this coloring case? anything related to this problem, it would be nice to mention it here.