Bounded Stable Sets: Polytopes and Colorings
Jeannette Janssen, Kyriakos Kilakos · SIAM Journal on Discrete Mathematics · 1999
A k-stable set in a graph is a stable set of size at most k. We study the convex hull of the k-stable sets of a graph, aiming for a complete inequality description. We also consider colorings of weighted graphs by k-stable sets, aiming for a relation between the values of an optimal coloring and an optimal fractional coloring. Results for k=2 and k=3 as well as a number of general conjectures linking fractional and integral colorings are given.