Clique-stable set separation in perfect graphs with no balanced skew-partitions

DOI10.1016/j.disc.2016.02.005zbMath1333.05225arXiv1312.2730OpenAlexW1738420676MaRDI QIDQ267214

Aurélie Lagoutte, Théophile Trunck

Publication date: 8 April 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

perfect graph2-joinclique-stable set separationtrigraph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Perfect graphs (05C17)

Related Items (4)

Excluding hooks and their complements ⋮ On the binary and Boolean rank of regular matrices ⋮ Decomposition techniques applied to the clique-stable set separation problem ⋮ Perfect Graphs with No Balanced Skew-Partition are 2-Clique-Colorable

Cites Work

• Unnamed Item
• Unnamed Item
• Clique versus independent set
• Coloring perfect graphs with no balanced skew-partitions
• The structure of bull-free graphs I -- three-edge-paths with centers and anticenters
• The structure of bull-free graphs II and III -- a summary
• The strong perfect graph theorem
• A bipartite analogue of Dilworth's theorem
• Perfect graphs of arbitrarily large clique-chromatic number
• Claw-free graphs. V. Global structure
• \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
• Expressing combinatorial optimization problems by linear programs
• Stable sets and polynomials
• The Erdős-Hajnal conjecture for paths and antipaths
• Decomposing Berge graphs and detecting balanced skew partitions
• Crossing patterns of semi-algebraic sets
• Perfect Graphs with No Balanced Skew-Partition are 2-Clique-Colorable
• The Erdös-Hajnal Conjecture-A Survey
• Linear vs. semidefinite extended formulations
• Berge trigraphs

This page was built for publication: Clique-stable set separation in perfect graphs with no balanced skew-partitions