کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
4949889 1364262 2017 7 صفحه PDF سفارش دهید دانلود کنید
عنوان انگلیسی مقاله
On color-critical (P5,co-P5)-free graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On color-critical (P5,co-P5)-free graphs
چکیده انگلیسی

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
نویسندگان
, , , , , ,