کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421115 | 684142 | 2015 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Domination, coloring and stability in P5P5-reducible graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A graph GG is P5P5-reducible if every vertex of GG lies in at most one induced P5P5 (path on five vertices). We show that a number of interesting results concerning P5P5-free graphs can be extended to P5P5-reducible graphs, namely: the existence of a dominating clique or P3P3, the fact that kk-colorability can be decided in polynomial time (for fixed kk), and the fact that a maximum stable set can be found in polynomial time in the class of kk-colorable P5P5-reducible graphs (for fixed kk).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 184, 31 March 2015, Pages 122–129
Journal: Discrete Applied Mathematics - Volume 184, 31 March 2015, Pages 122–129
نویسندگان
Jean-Luc Fouquet, Frédéric Maffray,