Article ID Journal Published Year Pages File Type
1143475 Operations Research Letters 2008 4 Pages PDF
Abstract

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

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
A one-to-one correspondence between colorings and stable sets
Authors
, ,