| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427547 | Information Processing Letters | 2010 | 5 Pages |
Abstract
Let G be a graph, x,y∈V(G), and ϕ:V(G)→[k] a k-colouring of G such that ϕ(x)=ϕ(y). If then the following question is NP-complete: Does there exist a k-colouring ϕ′ of G such that ϕ′(x)≠ϕ′(y)? Conversely, if then the problem is polynomial time.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
