کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650631 | 1632449 | 2006 | 28 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Which claw-free graphs are strongly perfect? Which claw-free graphs are strongly perfect?](/preview/png/4650631.png)
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].
Journal: Discrete Mathematics - Volume 306, Issues 19–20, 6 October 2006, Pages 2602–2629