Partitionable graphs, circle graphs, and the Berge strong perfect graph conjecture

DOI10.1016/0012-365X(83)90005-5zbMath0507.05052OpenAlexW2000311417WikidataQ123024354 ScholiaQ123024354MaRDI QIDQ1837210

Mark A. Buckingham, Martin Charles Golumbic

Publication date: 1983

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

Full work available at URL: https://doi.org/10.1016/0012-365x(83)90005-5

zbMATH Keywords

intersection graphperfect graphpartitionable graphcircle graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

On the structure of certain intersection graphs ⋮ An approach to solving \(A^{k}=J-I\) ⋮ The edge intersection graphs of paths in a tree ⋮ Interval graphs and related topics

Cites Work

• The validity of the strong perfect-graph conjecture for \((K_4-e)\)-free graphs
• Graphical properties related to minimal imperfection
• The strong perfect graph conjecture for toroidal graphs
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
• Almost integral polyhedra related to certain combinatorial optimization problems
• Critical perfect graphs and perfect 3-chromatic graphs
• Combinatorial designs related to the strong perfect graph conjecture
• A characterization of perfect graphs
• Normal hypergraphs and the perfect graph conjecture
• Coloring a Family of Circular Arcs
• Perfect zero–one matrices
• The Strong Perfect Graph Conjecture for Planar Graphs
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• On the strong perfect graph conjecture
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item