<p>If you can solve this problem, it implies a coloring algorithm for <a href="http://en.wikipedia.org/wiki/Uniquely_colorable_graph" rel="nofollow">Uniquely colorable graphs</a>.</p>

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

CC BY-SA 3.0
2013-07-08T15:19:07.590Z
[Unique 3-Colorability is as hard as Unique Satisfiability](http://dl.acm.org/citation.cfm?id=1013869)
Austin Buchanan
CC BY-SA 4.0
2021-04-08T05:24:20.453Z
@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
CC BY-SA 4.0
2021-04-08T05:26:26.607Z
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] (https://www.sciencedirect.com/science/article/pii/0012365X80902368).
Cyriac Antony
CC BY-SA 3.0
2013-04-30T03:56:54.783Z
2013-04-30T03:56:54.783Z
Igor Shinkar
<p>Add the edge $(u,v)$. Your property holds if and only if $G$ is no longer $k$-colorable.</p>

CC BY-SA 3.0
2013-04-30T09:45:55.460Z
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
CC BY-SA 3.0
2013-05-01T20:59:38.887Z
There was a mistake in the original answer. The current answer should work.
Yuval Filmus
CC BY-SA 3.0
2013-04-30T03:23:23.353Z
2013-04-30T14:35:55.660Z
2013-04-30T14:35:55.660Z
Yuval Filmus
<p>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$?</p>

<p>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.</p>

<p>Any thoughts?</p>

CC BY-SA 3.0
2013-04-29T23:55:18.387Z
Add the edge $(u,v)$. Your property holds if and only if $G$ is still $k$-colorable.
Yuval Filmus
CC BY-SA 3.0
2013-04-30T03:02:26.087Z
Ah, very good. Will you make this an answer?
Tyson Williams
CC BY-SA 3.0
2013-05-01T03:03:39.377Z
You should specify that they should take the same color _in every k-coloring_. Otherwise, the problem is not interesting.
Austin Buchanan
CC BY-SA 3.0
2013-05-01T13:49:18.893Z
@Austin Yes, this is what I meant. Thanks for the correction.
Tyson Williams
<cc.complexity-theory><np-hardness><graph-colouring>
Decision problem related to coloring
Tyson Williams
# Decision problem related to coloring

(Asked by: username_0 on 2013-04-29)

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?

**Tags:** cc.complexity-theory, np-hardness, graph-colouring

> **Comments:**
> **username_1**: Add the edge $(u,v)$. Your property holds if and only if $G$ is still $k$-colorable.  
> **username_0**: Ah, very good. Will you make this an answer?  
> **username_2**: You should specify that they should take the same color _in every k-coloring_. Otherwise, the problem is not interesting.  
> **username_0**: @Austin Yes, this is what I meant. Thanks for the correction.  

---

## 2 answers

### Answer by username_1 on 2013-04-30. Score: 9 | Accepted answer

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

> **Comments:**
> **username_5**: 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.  
> **username_1**: There was a mistake in the original answer. The current answer should work.  

---

### Answer by username_3 on 2013-04-30. Score: 3

If you can solve this problem, it implies a coloring algorithm for [Uniquely colorable graphs](http://en.wikipedia.org/wiki/Uniquely_colorable_graph).

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

> **Comments:**
> **username_2**: [Unique 3-Colorability is as hard as Unique Satisfiability](http://dl.acm.org/citation.cfm?id=1013869)  
> **username_4**: @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.  
> **username_4**: 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] (https://www.sciencedirect.com/science/article/pii/0012365X80902368).  

---

