Article ID Journal Published Year Pages File Type
4650631 Discrete Mathematics 2006 28 Pages PDF
Abstract

A set SS of pairwise nonadjacent vertices in an undirected graph GG is called a stable transversal   of GG if SS meets every maximal (with respect to set-inclusion) clique of GG. GG is called strongly perfect   if all its induced subgraphs (including GG itself) have stable transversals. A claw   is a graph consisting of vertices a,b,c,da,b,c,d and edges ab,ac,adab,ac,ad. We characterize claw-free strongly perfect graphs by five infinite families of forbidden induced subgraphs. This result—whose validity had been conjectured by Ravindra [Research problems, Discrete Math. 80 (1990) 105–107]—subsumes the characterization of strongly perfect line-graphs that was discovered earlier by Ravindra [Strongly perfect line graphs and total graphs, Finite and Infinite Sets. Colloq. Math. Soc. János Bolyai 37 (1981) 621–633].

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,