A chair is a graph with nodes \(a,b,c,d,e\) and edges \(ab,bc, cd,be\). The author proves that the strong perfect graph conjecture is true for chair-free graphs. The proof technique uses the properties of minimal imperfect graphs (MIGs) dicovered by Lovász, Padberg, Chvátal, and Sebő and the reduction operation introduced by Lovász and Plummer. If \(C\) is a maximal clique in a graph \(G=(V,E)\), the reduction of \(G\) with respect to \(C\) is the graph \(G|C=(V|C, E|C)\) where \(V|C=V-C\) and \(E|C= (E-\{uv\in E\mid u\in C\}) \cup \{uv\mid \{u,v\} \subseteq V-C\) and \(N_G(\{u,v\}) \supseteq C\} \). Further, \(C\) is reducible in \(G\) iff \(\alpha (G|C)= \alpha (G)-1\). Some of the important steps in the long proof are: (1) If \(G\) is a MIG with \(\alpha (G)\geq 3\) and \(C\) is a reducible clique of size \(\omega\) in \(G\), then \(G|C\) is an imperfect graph. (2) Every chair-free MIG has a reducible clique of size \(\omega\). (3) If \(C\) is a reducible clique in a chair-free graph \(G\) without odd holes, then \(G|C\) contains no odd hole. (4) If \(C\) is a reducible clique in a chair-free MIG \(H\) which is also Berge, and \(H'\) is a minimal imperfect subgraph of \(H|C\) which is also Berge, then \(H'\) is chair-free.
- A characterization of perfect graphs
- A mickey-mouse decomposition theorem
- Bull-free Berge graphs are perfect
- Coloring perfect \((K_ 4\)-e)-free graphs
- Critical perfect graphs and perfect 3-chromatic graphs
- scientific article; zbMATH DE number 956849 (Why is no real title available?)
- Matching theory
- New classes of Berge perfect graphs
- Normal hypergraphs and the perfect graph conjecture
- On a property of the class of n-colorable graphs
- On certain polytopes associated with graphs
- On critical edges in minimal imperfect graphs
- On the strong perfect graph conjecture
- Paw-free graphs
- Perfect zero–one matrices
- Stability number of bull- and chair-free graphs
- Star-cutsets and perfect graphs
- The rank facets of the stable set polytope for claw-free graphs
- The strong perfect graph conjecture for pan-free graphs
- The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
- The validity of the strong perfect-graph conjecture for (K₄-e)-free graphs
- Topics on perfect graphs
- Two classes of perfect graphs
- The strong perfect graph conjecture: 40 years of attempts, and its resolution
- Bull-free Berge graphs are perfect
- On minimal imperfect graphs without induced P₅
- New classes of Berge perfect graphs
- Classes of perfect graphs
- scientific article; zbMATH DE number 2230322 (Why is no real title available?)
- Novel evolutionary models and applications to sequence alignment problems
This page was built for publication: Chair-free Berge graphs are perfect
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1376074)
