کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420914 | 683998 | 2007 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The harmonious coloring problem is NP-complete for interval and permutation graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The harmonious coloring problem is NP-complete for interval and permutation graphs The harmonious coloring problem is NP-complete for interval and permutation graphs](/preview/png/420914.png)
چکیده انگلیسی
In this paper, we prove that the harmonious coloring problem is NP-complete for connected interval and permutation graphs. Given a simple graph G, a harmonious coloring of G is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number is the least integer k for which G admits a harmonious coloring with k colors. Extending previous work on the NP-completeness of the harmonious coloring problem when restricted to the class of disconnected graphs which are simultaneously cographs and interval graphs, we prove that the problem is also NP-complete for connected interval and permutation graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 155, Issue 17, 15 October 2007, Pages 2377–2382
Journal: Discrete Applied Mathematics - Volume 155, Issue 17, 15 October 2007, Pages 2377–2382
نویسندگان
Katerina Asdre, Kyriaki Ioannidou, Stavros D. Nikolopoulos,