Star-cutsets and perfect graphs (Q1121289)

This paper presents a general structure for understanding various known techniques for producing a new perfect graph \(G^*\) out of a given pair of old perfect graphs \(G_ 1,G_ 2\). A common property of these techniques is that: if an induced subgraph F of \(G^*\) (with F having at least three vertices) is an induced subgraph of neither \(G_ 1\) nor \(G_ 2\), then F has a star-cutset or its complement \(F^ c\) is disconnected. Here a star-cutset is a set of vertices that form a cutset and whose induced subgraph contains some vertex adjacent to all others in the cutset. The star closure \({\mathcal C}^*\) of a class \({\mathcal C}\) of graphs is recursively defined by the rules: (i) if \(G\in {\mathcal C}\), then \(G\in {\mathcal C}^*\); and (ii) if G or \(G^ c\) has a star-cutset and if G-v\(\in {\mathcal C}^*\) for all v in G, then \(G\in {\mathcal C}^*\). The author proves that two classes of strongly perfect graphs, the Meyniel graphs and perfectly orderable graphs, are in the star closure of the class of bipartite graphs.