Stable set bonding in perfect graphs and parity graphs (Q1321990)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Stable set bonding in perfect graphs and parity graphs |
scientific article |
Statements
Stable set bonding in perfect graphs and parity graphs (English)
0 references
10 August 1994
0 references
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.
0 references
independent sets
0 references
stable sets
0 references
parity graphs
0 references
perfect graphs
0 references
composition operation
0 references