کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421052 | 684022 | 2006 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Precoloring extension on unit interval graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In the precoloring extension problem a graph is given with some of the vertices having preassigned colors and it has to be decided whether this coloring can be extended to a proper k-coloring of the graph. Answering an open question of Hujter and Tuza [Precoloring extension. III. Classes of perfect graphs, Combin. Probab. Comput. 5 (1) (1996) 35–56], we show that the precoloring extension problem is NP-complete on unit interval graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 154, Issue 6, 15 April 2006, Pages 995–1002
Journal: Discrete Applied Mathematics - Volume 154, Issue 6, 15 April 2006, Pages 995–1002
نویسندگان
Dániel Marx,