On the facets of the stable set polytope of quasi‐line graphs

On the facets of the stable set polytope of quasi‐line graphs

0.00 Avg rating0 Votes
Article ID: iaor20115237
Volume: 39
Issue: 3
Start Page Number: 208
End Page Number: 212
Publication Date: May 2011
Journal: Operations Research Letters
Authors:
Keywords: polytopes
Abstract:

While the Ben Rebea Theorem provides a complete linear description of the stable set polytope of quasi‐line graphs, no minimal description is currently available. In this paper, we shed some light on this question by (1) showing that any facet of this polytope is such that the restriction of the inequality to maximal coefficients yields a rank facet and (2) providing a complete description of the strongly minimal facets. We also show that those results support two conjectures refining the Ben Rebea Theorem.

Reviews

Required fields are marked *. Your email address will not be published.