Article ID Journal Published Year Pages File Type
4648688 Discrete Mathematics 2011 4 Pages PDF
Abstract

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.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,