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$ – Yuval Filmus Apr 29 '13 at 23:55
  • $\begingroup$ Ah, very good. Will you make this an answer? $\endgroup$ – Tyson Williams Apr 30 '13 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$ – Austin Buchanan May 1 '13 at 3:03
  • $\begingroup$ @Austin Yes, this is what I meant. Thanks for the correction. $\endgroup$ – 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.

  • 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 '13 at 9:45
  • $\begingroup$ There was a mistake in the original answer. The current answer should work. $\endgroup$ – 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.

  • $\begingroup$ Unique 3-Colorability is as hard as Unique Satisfiability $\endgroup$ – Austin Buchanan Jul 8 '13 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$ – Cyriac Antony Apr 8 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$ – Cyriac Antony Apr 8 at 5:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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