کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949901 | 1364262 | 2017 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Vertex coloring of graphs with few obstructions
ترجمه فارسی عنوان
رنگ آمیزی ورتکس از گراف ها با چند مانع
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
رنگ آمیزی ورتکس، الگوریتم زمان چندجملهای، ردیابی پارامتر پارامتر
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We study the vertex coloring problem in classes of graphs defined by finitely many forbidden induced subgraphs. Of our special interest are the classes defined by forbidden induced subgraphs with at most 4 vertices. For all but three classes in this family we show either NP-completeness or polynomial-time solvability of the problem. For the remaining three classes we prove fixed-parameter tractability. Moreover, for two of them we give a 3/2 approximation polynomial algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 273-280
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 273-280
نویسندگان
V.V. Lozin, D.S. Malyshev,