Cutsets in perfect and minimal imperfect graphs (Q2758337)

In this eighth chapter of the book ``Perfect graphs'', the author surveys the results on cutsets in perfect and minimal imperfect graphs. The concept of \(F\)-bonding and the closure of a set of graphs under a predicate are employed to construct larger classes of perfect graphs. NEWLINENEWLINENEWLINEIf two graphs \(G_1\) and \(G_2\) have a graph \(F\) as an induced subgraph, the \(F\)-bonding of \(G_1\) and \(G_2\) is obtained by identifying the corresponding vertices of \(F\) in \(G_1\) and \(G_2\). The review starts with the observation that clique-bonding (when \(F\) is a clique) alone preserves perfection (in general) and the corollary that no MIG (minimal imperfect graph) can contain a clique cutset. Results of Tucker, Chvátal and Cornuéjoles-Reed on non-existence of a stable cutset, a star cutset, and a complete multipartite cutset (respectively) in MIGs (with suitable modifications) are reviewed. Chvátal's conjecture that no MIG admits a skew partition, Olariu's result on partitionable cutsets and Hoàng's partial result on the skew partition conjecture are also dealt with. NEWLINENEWLINENEWLINESection 4 starts with the definition of the closure \(\mathcal{G}^P\) of a class of graphs \(\mathcal{G}\) under a predicate \(P\) by the rules: (i) if \(G\in \mathcal{G}\), then \(G\in \mathcal{G}^P\); and (ii) if \(G\) satisfies \(P\) and if \(G-v \in \mathcal{G}^P\) for every vertex \(v\) in \(G\), then \(G\in \mathcal{G}^P\). NEWLINENEWLINENEWLINEObserving that if \(\mathcal{G}\) is a class of perfect graphs and \(P\) is a property a MIG cannot have then every graph in \(\mathcal{G}^P\) is also perfect, the author considers the following predicate cases: (1) * = \(G\) or \(\overline{G}\) has a star cutset, (2) \(\pi\) = \(G\) is either a clique or a stable set or \(G\) has a partitionable cutset, (3) \(c=G\) has a clique cutset, (4) \(s=G\) has a stable cutset, and reviews the results for several classes of perfect graphs obtained as included in \(\mathcal{G}^P\) for different choices of \(\mathcal{G}\). In particular \(\text{Triv}^\pi\) is the class of perfect graphs, where Triv is the class of graphs with at most two vertices. These take up Sections 4, 5 and 6. NEWLINENEWLINENEWLINESections 7 and 8 are devoted to an examination of the status of several conjectures related to the Strong Perfect Graph Conjecture (SPGC). These include the ones imposing conditions on Berge graphs \(G\) like: neither \(G\) nor \(\overline{G}\) has a star cutset/a stable cutset/an even pair/an odd pair/a skew partition, and two conjectures of Sebö which are together equivalent to the SPGC and attempt to bridge the gap between partitionable graphs and MIGs through the concept of a small transversal.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00015].