On Non-Rank Facets of Stable Set Polytopes of Webs with Clique Number Four
Please always quote using this URN: urn:nbn:de:0297-zib-7238
- Graphs with circular symmetry, called webs, are relevant w.r.t. describing the stable set polytopes of two larger graph classes, quasi-line graphs and claw-free graphs. Providing a decent linear description of the stable set polytopes of claw-free graphs is a long-standing problem. However, even the problem of finding all facets of stable set polytopes of webs is open. So far, it is only known that stable set polytopes of webs with clique number $\leq 3$ have rank facets only while there are examples with clique number $>4$ having non-rank facets.
Author: | Arnaud Pecher, Annegret Wagler |
---|---|
Document Type: | ZIB-Report |
Tag: | (non-)rank facet; rank-perfect graph; stable set polytope; web |
MSC-Classification: | 05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C17 Perfect graphs |
05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C69 Dominating sets, independent sets, cliques | |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut | |
Date of first Publication: | 2003/02/06 |
Series (Serial Number): | ZIB-Report (03-01) |
ZIB-Reportnumber: | 03-01 |
Published in: | Appeared in: Discrete Applied Mathematics 154 (2006) 1408-1415 |