کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6423289 1342323 2015 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
ترجمه فارسی عنوان
پیچیدگی مشکل رنگ آمیزی 3 در نبود یک جفت کوچک زیرگراف القا شده ممنوع است
کلمات کلیدی
مشکل رنگ آمیزی 3 پیچیدگی محاسباتی، الگوریتم زمان چندجملهای،
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

We completely determine the complexity status of the 3-colorability problem for hereditary graph classes defined by two forbidden induced subgraphs with at most five vertices.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 338, Issue 11, 6 November 2015, Pages 1860-1865
نویسندگان
,