Article ID Journal Published Year Pages File Type
1143320 Operations Research Letters 2011 5 Pages PDF
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.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,