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

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