On the linear extension complexity of stable set polytopes for perfect graphs

DOI10.1016/j.ejc.2018.02.014zbMath1416.05120arXiv1706.05496OpenAlexW1436457511MaRDI QIDQ2311370

Monique Laurent, Hao Hu

Publication date: 10 July 2019

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

Full work available at URL: https://arxiv.org/abs/1706.05496

zbMATH Keywords

basic perfect graphsstable set polytopes of perfect graphs

Mathematics Subject Classification ID

Perfect graphs (05C17) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Unnamed Item
• Colouring perfect graphs with bounded clique number
• Coloring perfect graphs with no balanced skew-partitions
• Smallest compact formulation for the permutahedron
• Stable sets and graphs with no even holes
• Combinatorial optimization with 2-joins
• The strong perfect graph theorem
• Star-cutsets and perfect graphs
• The ellipsoid method and its consequences in combinatorial optimization
• Using separation algorithms to generate mixed integer model reformulations
• On the perfect graph conjecture
• On certain polytopes associated with graphs
• Extension complexity of stable set polytopes of bipartite graphs
• Combinatorial bounds on nonnegative rank and extended formulations
• Compositions for perfect graphs
• Some \(0/1\) polytopes need exponential size extended formulations
• A characterization of perfect graphs
• Normal hypergraphs and the perfect graph conjecture
• Exponential Lower Bounds for Polytopes in Combinatorial Optimization
• Lower Bounds on the Size of Semidefinite Programming Relaxations
• The Matching Polytope has Exponential Extension Complexity
• Lifts of Convex Sets and Cone Factorizations
• Fast Skew Partition Recognition
• Berge trigraphs
• Extended formulations in combinatorial optimization