Skew partitions in perfect graphs

DOI10.1016/j.dam.2007.05.054zbMath1147.05035OpenAlexW2048827438WikidataQ57535774 ScholiaQ57535774MaRDI QIDQ2482110

Bruce A. Reed

Publication date: 16 April 2008

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

Full work available at URL: https://doi.org/10.1016/j.dam.2007.05.054

zbMATH Keywords

perfect graphsstrong perfect graph conjectureskew partitions

Mathematics Subject Classification ID

Perfect graphs (05C17)

Related Items (7)

Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday) ⋮ Fast Skew Partition Recognition ⋮ Decomposing Berge graphs and detecting balanced skew partitions ⋮ The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory ⋮ Skew partition sandwich problem is NP-complete ⋮ Defending Planar Graphs against Star-Cutsets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Weakly triangulated graphs
• The strong perfect graph theorem
• Bull-free Berge graphs are perfect
• Star-cutsets and perfect graphs
• Some properties of minimal imperfect graphs
• An algorithm for finding clique cut-sets
• Algorithms on clique separable graphs
• Complete multi-partite cutsets in minimal imperfect graphs
• On certain polytopes associated with graphs
• A generalization of Chvátal's star-cutset lemma
• About skew partitions in minimal imperfect graphs
• Compositions for perfect graphs
• Normal hypergraphs and the perfect graph conjecture
• On a property of the class of n-colorable graphs
• Transitiv orientierbare Graphen

This page was built for publication: Skew partitions in perfect graphs