Split-neighbourhood graphs and the strong perfect graph conjecture

DOI10.1006/JCTB.1995.1021MaRDI QIDQ1892848zbMATH OpenOpenAlexFDO

Authors Frédéric Maffray, Myriam Preissmann

Publication date 2 July 1995

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jctb.1995.1021

zbMATH Keywords

Berge's strong perfect graph conjecturechromatic numbercliqueperfect graphpolynomially recognizablesplit-neighbourhoodstable set

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

We introduce the class of graphs such that every induced subgraph possesses a vertex whose neighbourhood can be split into a clique and a stable set. We prove that this class satisfies Berge's strong perfect graph conjecture. This class contains several well-known classes of (perfect) graphs and is polynomially recognizable.

Recommendations

• Recognizing Perfect 2-Split Graphs
• The strong perfect graph theorem
• Classes of perfect graphs
• On a Class of P ₅ -Free Graphs
• Progress on perfect graphs

Cited in

(17)

• Dynamically maintaining split graphs
• The strong perfect graph conjecture: 40 years of attempts, and its resolution
• Neighborhood perfect graphs
• On minimal imperfect graphs without induced P₅
• Coloring perfect degenerate graphs
• Split permutation graphs
• Subdivided claws and the clique-stable set separation property
• Characterizing graph classes using twin vertices of regular induced subgraphs
• Advances in Aharoni-Hartman-Hoffman's conjecture for split digraphs
• Classes of perfect graphs
• Forbidden graphs for classes of split-like graphs
• scientific article; zbMATH DE number 1696523 (Why is no real title available?)
• On split and almost CIS-graphs
• scientific article; zbMATH DE number 3908483 (Why is no real title available?)
• Fast recognition of doubled graphs
• scientific article; zbMATH DE number 2204095 (Why is no real title available?)
• Nonsplit Graphs with Split Maximal Induced Subgraphs

This page was built for publication: Split-neighbourhood graphs and the strong perfect graph conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1892848)