Stable set bonding in perfect graphs and parity graphs (Q1321990): Difference between revisions

Let \(G_ 1= (V_ 1\cup S_ 1, E_ 1)\) and \(G_ 2= (V_ 2\cup S_ 2, E_ 2)\) be connected graphs which each have stable sets \(S_ 1\) (resp. \(S_ 2)\) of the same size. Let \(\Phi_ S\) be the operation which forms \(G= (V,E)\) from \(G_ 1\) and \(G_ 2\) by identification of \(S_ 1\) and \(S_ 2\), where \(S\subseteq V\) corresponds to \(S_ 1\) and \(S_ 2\). If all minimal chains in \(G_ 1\) and \(G_ 2\) linking \(v\) to \(w\) for \(v, w\in S\) have the same parity, and if \(H_ 1\) and \(H_ 2\) are parity graphs, where \(G_ 1\Phi_ S H_ 2\), \(H_ 1\Phi_ S G_ 2\), and \(H_ 1\Phi_ S H_ 2\) are perfect graphs then \(G_ 1\Phi_ S G_ 2\) is also perfect. This leads to a new composition operation which preserves perfection.