Abstract
Graphs with circular symmetry, called webs, are crucial for describing the stable set polytopes of two larger graph classes, quasi-line graphs[8,12] and claw-free graphs [7,8]. Providing a complete linear description of the stable set polytopes of claw-free graphs is a long-standing problem [9]. Ben Rebea conjectured a description for quasi-line graphs, see [12]; Chudnovsky and Seymour [2] verified this conjecture recently for quasi-line graphs not belonging to the subclass of fuzzy circular interval graphs and showed that rank facets are required in this case only. Fuzzy circular interval graphs contain all webs and even the problem of finding all facets of their stable set polytopes is open. So far, it is only known that stable set polytopes of webs with clique number ≤3 have rank facets only [5,17] while there are examples with clique number ≥4 having non-rank facets [10_12,15].
In this paper we prove, building on a construction for non-rank facets from [16], that the stable set polytopes of almost all webs with clique number ≥5 admit non-rank facets. This adds support to the belief that these graphs are indeed the core of Ben Rebea's conjecture. Finally, we present a conjecture how to construct all facets of the stable set polytopes of webs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The Strong Perfect Graph Theorem, to appear in: Annals of Mathematics.
Chudnovsky, M., Seymour, P.: Claw-free graphs VI. The structure of quasi-line graphs. Manuscript, 2004
Chvátal, V.: On Certain Polytopes Associated with Graphs. J. Combin. Theory B 18, 138–154 (1975)
Chvátal, V.: On the Strong Perfect Graph Conjecture. J. Combin. Theory B 20, 139–141 (1976)
Dahl, G.: Stable Set Polytopes for a Class of Circulant Graphs. SIAM J. Optim. 9, 493–503 (1999)
Edmonds, J.R., Pulleyblank, W.R.: Facets of 1-Matching Polyhedra. In: C. Berge, D.R. Chuadhuri (eds.), Hypergraph Seminar. Springer, Berlin Heidelberg, 1974, pp. 214–242
Galluccio, A., Sassano, A.: The Rank Facets of the Stable Set Polytope for Claw-Free Graphs. J. Comb. Theory B 69, 1–38 (1997)
Giles, G., Trotter, L.E., Jr.: On Stable Set Polyhedra for K1,3-free Graphs. J. Comb. Theory B 31, 313–326 (1981)
Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin Heidelberg, 1988
Kind, J.: Mobilitätsmodelle für zellulare Mobilfunknetze: Produktformen und Blockierung. PhD thesis, RWTH Aachen, 2000
Liebling, T.M., Oriolo, G., Spille, B., Stauffer, G.: On Non-Rank Facets of the Stable Set Polytope of Claw-Free Graphs and Circulant Graphs. Submitted to Math. Methods of Operations Research
Oriolo, G.: Clique Family Inequalities for the Stable Set Polytope for Quasi-Line Graphs. In: Special Issue on Stability Problems, Discrete Applied Math. 132, 185–201 (2003)
Oriolo, G., Stauffer, G.: On the Stable Set Polytope of Quasi-Line Graphs. Manuscript
Padberg, M.W.: Perfect Zero-One Matrices. Math. Programming 6, 180–196 (1974)
Pêcher, A., Wagler, A.: On Non-Rank Facets of Stable Set Polytopes of Webs with Clique Number Four. To appear in: Discrete Applied Mathematics
Pêcher, A., Wagler, A.: A construction for non-rank facets of stable set polytopes of webs. To appear in: European Journal of Combinatorics
Trotter, L.E., Jr.: A Class of Facet Producing Graphs for Vertex Packing Polyhedra. Discrete Math. 12, 373–388 (1975)
Wagler, A.: Antiwebs are rank-perfect. Quarterly Journal of the Belgian, French and Italian OR Societies 2, 149–152 (2004)
Author information
Authors and Affiliations
Corresponding author
Additional information
Received: April, 2004
Rights and permissions
About this article
Cite this article
Pêcher, A., Wagler, A. Almost all webs are not rank-perfect. Math. Program. 105, 311–328 (2006). https://doi.org/10.1007/s10107-005-0655-7
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-005-0655-7