A construction for non-rank facets of stable set polytopes of webs

DOI10.1016/J.EJC.2006.06.013MaRDI QIDQ852709zbMATHOpenAlexFDO

Authors Arnaud Pêcher, Annegret K. Wagler

Publication date 15 November 2006

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejc.2006.06.013

zbMATH Keywords

graphscombinatorial optimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Recommendations

• On non-rank facets of stable set polytopes of webs with clique number four
• Almost all webs are not rank-perfect
• Antiwebs are rank-perfect
• On non-rank facets of the stable set polytope of claw-free graphs and circulant graphs
• The rank facets of the stable set polytope for claw-free graphs

Cites work

• scientific article; zbMATH DE number 3496213 (Why is no real title available?)
• scientific article; zbMATH DE number 3437188 (Why is no real title available?)
• scientific article; zbMATH DE number 2044950 (Why is no real title available?)
• A class of facet producing graphs for vertex packing polyhedra
• Almost all webs are not rank-perfect
• Antiwebs are rank-perfect
• Circular Ones Matrices and the Stable Set Polytope of Quasi-Line Graphs
• Clique family inequalities for the stable set polytope of quasi-line graphs.
• Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem
• Geometric algorithms and combinatorial optimization
• Graphical properties related to minimal imperfection
• Mobility models for cellular mobile radiotelephone networks: Product forms and blocking
• On certain polytopes associated with graphs
• On non-rank facets of stable set polytopes of webs with clique number four
• On non-rank facets of the stable set polytope of claw-free graphs and circulant graphs
• On stable set polyhedra for K//(1,3)free graphs
• On the strong perfect graph conjecture
• Perfect zero–one matrices
• Stable Set Polytopes for a Class of Circulant Graphs
• The rank facets of the stable set polytope for claw-free graphs
• The strong perfect graph theorem

Cited in

(6)

• On the set covering polyhedron of circulant matrices
• A new lifting theorem for vertex packing
• On the \(k\)-dominating set polytope of web graphs
• On non-rank facets of stable set polytopes of webs with clique number four
• Facet-inducing web and antiweb inequalities for the graph coloring polytope
• Almost all webs are not rank-perfect

This page was built for publication: A construction for non-rank facets of stable set polytopes of webs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q852709)