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

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