# Decision problem related to coloring

Given a $k$-colorable graph $G$ and vertices $u$ and $v$ of $G$, what is the complexity of deciding if every $k$-coloring of $G$ must assign the same color to both $u$ and $v$?

It does not seem obvious to me how to use the above problem as an oracle to construct a coloring, so it is conceivable that this problem is efficiently decidable. On the other hand, minor variants of NP-hard problems, such as this one, typically remain NP-hard. But most of all, I do not know what problem is a good choice to reduce from.

Any thoughts?

• Add the edge $(u,v)$. Your property holds if and only if $G$ is still $k$-colorable. – Yuval Filmus Apr 29 '13 at 23:55
• Ah, very good. Will you make this an answer? – Tyson Williams Apr 30 '13 at 3:02
• You should specify that they should take the same color in every k-coloring. Otherwise, the problem is not interesting. – Austin Buchanan May 1 '13 at 3:03
• @Austin Yes, this is what I meant. Thanks for the correction. – Tyson Williams May 1 '13 at 13:49

Add the edge $(u,v)$. Your property holds if and only if $G$ is no longer $k$-colorable.
• Let $G$ be obtained from the complete graph with $n$ vertices by deleting the edge $uv$. Then $G$ is $(n-1)$-colourable and every $(n-1)$-colouring of $G$ must assign the same colour to both $u$ and $v$. But $G$ plus the edge $(u,v)$ is not $(n-1)$-colourable. – user13136 Apr 30 '13 at 9:45