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?

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

2 Answers 2


Add the edge $(u,v)$. Your property holds if and only if $G$ is no longer $k$-colorable.

  • 6
    $\begingroup$ 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. $\endgroup$
    – user13136
    Apr 30, 2013 at 9:45
  • $\begingroup$ There was a mistake in the original answer. The current answer should work. $\endgroup$ May 1, 2013 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.

  • $\begingroup$ Unique 3-Colorability is as hard as Unique Satisfiability $\endgroup$ Jul 8, 2013 at 15:19
  • $\begingroup$ @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. $\endgroup$ Apr 8, 2021 at 5:24
  • $\begingroup$ 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). $\endgroup$ Apr 8, 2021 at 5:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.