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

DOI10.1016/J.EJC.2006.06.013MaRDI QIDQ852709zbMATH OpenOpenAlexFDO

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)