Almost all webs are not rank-perfect

DOI10.1007/s10107-005-0655-7zbMath1083.05032OpenAlexW2019885282MaRDI QIDQ2583128

Annegret K. Wagler, Arnaud Pêcher

Publication date: 13 January 2006

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-005-0655-7

zbMATH Keywords

stable set polytopenon-rank facetrank-facet

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Perfect graphs (05C17)

Related Items (14)

Minor related row family inequalities for the set covering polyhedron of circulant matrices ⋮ A construction for non-rank facets of stable set polytopes of webs ⋮ On dominating set polyhedra of circular interval graphs ⋮ Facet-inducing web and antiweb inequalities for the graph coloring polytope ⋮ On the facets of stable set polytopes of circular interval graphs ⋮ On the facets of the stable set polytope of quasi-line graphs ⋮ Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs ⋮ A note on the Chvátal-rank of clique family inequalities ⋮ Lifted, projected and subgraph-induced inequalities for the representatives \(k\)-fold coloring polytope ⋮ Unnamed Item ⋮ An integer programming approach for solving a generalized version of the Grundy domination number ⋮ On the set covering polyhedron of circulant matrices ⋮ Lovász-Schrijver PSD-Operator on Claw-Free Graphs ⋮ A new lifting theorem for vertex packing

Cites Work

• Unnamed Item
• Unnamed Item
• A construction for non-rank facets of stable set polytopes of webs
• The strong perfect graph theorem
• Clique-circulants and the stable set polytope of fuzzy circular interval graphs
• On stable set polyhedra for K//(1,3)free graphs
• Geometric algorithms and combinatorial optimization
• A class of facet producing graphs for vertex packing polyhedra
• The rank facets of the stable set polytope for claw-free graphs
• On certain polytopes associated with graphs
• Clique family inequalities for the stable set polytope of quasi-line graphs.
• On non-rank facets of the stable set polytope of claw-free graphs and circulant graphs
• Antiwebs are rank-perfect
• Claw-free graphs. VII. Quasi-line graphs
• On non-rank facets of stable set polytopes of webs with clique number four
• Stable Set Polytopes for a Class of Circulant Graphs
• Perfect zero–one matrices
• On the strong perfect graph conjecture

This page was built for publication: Almost all webs are not rank-perfect