Some aspects of minimal imperfect graphs (Q2758338)

A graph \(G\) is perfect if, for each induced subgraph \(H\) of \(G\), the chromatic number \(\chi(H)\) of \(H\) is equal to the clique number \(\omega(H)\) of \(H\). A graph \(G\) is minimal imperfect if \(G\) is not perfect but every proper induced subgraph of \(G\) is perfect. A graph is partitionable if there exist some integers \(\alpha \geq 2\), \(\omega \geq 2\) such that \(G\) has exactly \(\alpha\omega + 1\) vertices and, for each vertex \(v\), \(G-v\) has both a partition of size \(\alpha\) into cliques and a partition of size \(\omega\) into stable sets. It is well known by the Lovász perfect graph theorem that minimal imperfect graphs are partitionable. Minimal imperfect graphs and partitionable graphs are important concepts in known attempts to prove the famous Berge strong perfect graph conjecture. The paper is a nice and comprehensive survey on these graphs. The authors also discuss several conjectures that may be stronger, weaker, equivalent, independent, or with unknown status compared to the strong perfect graph conjecture.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00015].