کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949889 | 1364262 | 2017 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On color-critical (P5,co-P5)-free graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A graph is k-critical if it is k-chromatic but each of its proper induced subgraphs is (kâ1)-colorable. It is known that the number of 4-critical P5-free graphs is finite, but there is an infinite number of k-critical P5-free graphs for each kâ¥5. We show that the number of k-critical (P5,P¯5)-free graphs is finite for every fixed k. Our result implies the existence of a certifying algorithm for k-coloring (P5,P¯5)-free graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 142-148
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 142-148
نویسندگان
Harjinder S. Dhaliwal, Angèle M. Hamel, ChÃnh T. Hoà ng, Frédéric Maffray, Tyler J.D. McConnell, Stefan A. Panait,