# 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. Commented Apr 29, 2013 at 23:55
• Ah, very good. Will you make this an answer? Commented Apr 30, 2013 at 3:02
• You should specify that they should take the same color in every k-coloring. Otherwise, the problem is not interesting. Commented May 1, 2013 at 3:03
• @Austin Yes, this is what I meant. Thanks for the correction. Commented May 1, 2013 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. Commented Apr 30, 2013 at 9:45
• By the way, given a graph $G$ and a $k$-colouring $f$ of $G$, it is NP-complete to test whether $f$ is the unique $k$-colouring of $G$ (upto permutation of colours) [Dailey, 1980] (sciencedirect.com/science/article/pii/0012365X80902368). Commented Apr 8, 2021 at 5:26