On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two |
| |
| Authors: | Elaine M Eschen Chính T Hoàng R Sritharan Lorna Stewart |
| |
| Institution: | aLane Department of Computer Science and Electrical Engineering, West Virginia University, Morgantown, WV 26506, United States;bDepartment of Physics and Computer Science, Wilfrid Laurier University, Waterloo, Canada;cComputer Science Department, The University of Dayton, Dayton, OH 45469, United States;dDepartment of Computing Science, University of Alberta, Edmonton, Alberta, Canada T6G 2E8 |
| |
| Abstract: | In an article Cheng (2009) 3] published recently in this journal, it was shown that when k≥3, the problem of deciding whether the distinguishing chromatic number of a graph is at most k is NP-hard. We consider the problem when k=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: | Distinguishing chromatic number Complexity |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
