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 no longer $k$-colorable.