# 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

## 2 Answers

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
• There was a mistake in the original answer. The current answer should work. – Yuval Filmus May 1 '13 at 20:59

If you can solve this problem, it implies a coloring algorithm for Uniquely colorable graphs.

Though, I'm not sure the problem of coloring uniquely colorable graphs is NP-hard.

• Unique 3-Colorability is as hard as Unique Satisfiability – Austin Buchanan Jul 8 '13 at 15:19
• @AustinBuchanan According to Barbanchon's paper Unique 3-colorability is DP-complete under polynomial time randomized reductions. Does that imply that the problem is NP-complete? (I suppose not). If I understand it right, randomized reductions does not prove hardness, but rather gather practical evidence for hardness. – Cyriac Antony Apr 8 at 5:24
• 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). – Cyriac Antony Apr 8 at 5:26