Stable set bonding in perfect graphs and parity graphs
type: Item
instance of: scholarly article
title: Stable set bonding in perfect graphs and parity graphs
zbMATH Open document ID: 0793.05119
published in: Journal of Combinatorial Theory. Series B
publication date: 1994-08-10T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 562378
zbMATH Keywords: independent sets
zbMATH Keywords: stable sets
zbMATH Keywords: parity graphs
zbMATH Keywords: perfect graphs
zbMATH Keywords: composition operation
author: Derek G. Corneil
author: Jean Fonlupt
MaRDI profile type: Publication
full work available at URL: jctb.1993.1049
OpenAlex ID: W2082173549
DOI: 10.1006/JCTB.1993.1049
description: scientific article; zbMATH DE number 562378