کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650631 1632449 2006 28 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Which claw-free graphs are strongly perfect?
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Which claw-free graphs are strongly perfect?
چکیده انگلیسی

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].

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 306, Issues 19–20, 6 October 2006, Pages 2602–2629
نویسندگان
,