کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648688 | 1342424 | 2011 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In an article Cheng (2009) [3] published recently in this journal, it was shown that when k≥3k≥3, the problem of deciding whether the distinguishing chromatic number of a graph is at most kk is NP-hard. We consider the problem when k=2k=2. In regards to the issue of solvability in polynomial time, we show that the problem is at least as hard as graph automorphism, but no harder than graph isomorphism.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 311, Issue 6, 28 March 2011, Pages 431–434
Journal: Discrete Mathematics - Volume 311, Issue 6, 28 March 2011, Pages 431–434
نویسندگان
Elaine M. Eschen, Chính T. Hoàng, R. Sritharan, Lorna Stewart,