Chair-free Berge graphs are perfect

DOI10.1007/BF03353015zbMath0891.05054MaRDI QIDQ1376074

Antonio Sassano

Publication date: 8 July 1998

Published in: Graphs and Combinatorics (Search for Journal in Brave)

zbMATH Keywords

strong perfect graph conjectureimperfect graphsmaximal cliquechairstar cut setreducible cliquechair-free graphMickey Mouse

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (5)

Novel evolutionary models and applications to sequence alignment problems ⋮ Classes of perfect graphs ⋮ Unnamed Item ⋮ On minimal imperfect graphs without induced \(P_5\) ⋮ The strong perfect graph conjecture: 40 years of attempts, and its resolution

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• The validity of the strong perfect-graph conjecture for \((K_4-e)\)-free graphs
• Topics on perfect graphs
• Coloring perfect \((K_ 4\)-e)-free graphs
• Matching theory
• Bull-free Berge graphs are perfect
• Paw-free graphs
• Two classes of perfect graphs
• The strong perfect graph conjecture for pan-free graphs
• Star-cutsets and perfect graphs
• Stability number of bull- and chair-free graphs
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
• Critical perfect graphs and perfect 3-chromatic graphs
• New classes of Berge perfect graphs
• The rank facets of the stable set polytope for claw-free graphs
• On certain polytopes associated with graphs
• On critical edges in minimal imperfect graphs
• A characterization of perfect graphs
• Normal hypergraphs and the perfect graph conjecture
• On a property of the class of n-colorable graphs
• Perfect zero–one matrices
• A mickey-mouse decomposition theorem
• On the strong perfect graph conjecture

This page was built for publication: Chair-free Berge graphs are perfect