Given a graph G, we construct an auxiliary graph &Gtilde; with &mmacr; vertices such that the set of all stable sets of &Gtilde; is in one-to-one correspondence with the set of all colorings of G. Then, we show that the Max-Coloring problem in G reduces to the Maximum Weighted Stable set problem in &Gtilde;.
