Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648688 | Discrete Mathematics | 2011 | 4 Pages |
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
Elaine M. Eschen, Chính T. Hoàng, R. Sritharan, Lorna Stewart,