کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421184 684158 2013 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
4-coloring HH-free graphs when HH is small
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
4-coloring HH-free graphs when HH is small
چکیده انگلیسی

The kk-Coloring problem is to test whether a graph can be colored with at most kk colors such that no two adjacent vertices receive the same color. If a graph GG does not contain a graph HH as an induced subgraph, then GG is called HH-free. For any fixed graph HH on at most six vertices, it is known that 33-Coloring is polynomial-time solvable on HH-free graphs whenever HH is a linear forest, and NP-complete otherwise. By solving the missing case P2+P3P2+P3, we prove the same result for 44-Coloring provided that HH is a fixed graph on at most five vertices.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 161, Issues 1–2, January 2013, Pages 140–150
نویسندگان
, , ,