<p>This <a href="https://www.sciencedirect.com/science/article/pii/S030439750400115X" rel="nofollow noreferrer">paper by Régis Barbanchon</a> might be of interest. From the abstract:</p>
<blockquote>
<p>We prove that the Satisfiability (resp. planar Satisfiability) problem
is parsimoniously P-time reducible to the 3-Colorability (resp. Planar
3-Colorability) problem, that means that the exact number of solutions
is preserved by the reduction, provided that 3-colorings are counted
modulo their six trivial color permutations. In particular, the
uniqueness of solutions is preserved, which implies that Unique
3-Colorability is exactly as hard as Unique Satisfiability in the
general case as well as in the planar case...</p>
</blockquote>

CC BY-SA 4.0
2021-04-21T19:10:21.960Z
2021-04-21T19:10:21.960Z
Austin Buchanan
<p>The <a href="http://en.wikipedia.org/wiki/Isolation_lemma">Isolation lemma</a> of Mulmuley, Vazirani, and Vazirani  can be used to show that certain $\mathsf{NP}$-complete problems can be reduced via randomized polytime reductions to the <em>unique</em> solution version of the problem. This hints that  the promise of a unique solution is not likely to make the problem significantly easier. </p>

<p>A specific example for such a reduction in the Mulmuley, Vazirani, and Vazirani paper <a href="http://cs.berkeley.edu/~vazirani/pubs/matching.pdf">(pdf)</a>
 is that CLIQUE can be reduced to UNIQUE CLIQUE via randomized polynomial time reductions. In this sense,  UNIQUE CLIQUE is (almost) as hard as CLIQUE.</p>

<blockquote>
  <p>Is there anything similar known about the UNIQUE $k$-COLORABILITY of graphs? </p>
</blockquote>

<p>It is worth noting that the promise of unique colorability seems to involve more structural consequences than the uniqueness of the maximum clique. </p>

CC BY-SA 3.0
2014-04-27T05:58:11.097Z
http://www.sciencedirect.com/science/article/pii/S030439750400115X
Austin Buchanan
CC BY-SA 3.0
2014-04-27T15:51:08.307Z
Thank you, the linked paper provides an interesting answer.
Andras Farago
CC BY-SA 4.0
2019-05-26T23:23:28.493Z
@AndrasFarago From the reference so $PLAN-3-COL$ problems are essentially to distinguish $3$ colorability from $4$ colorability since we have a parsimonious reduction?
Turbo
CC BY-SA 4.0
2021-04-21T17:46:50.197Z
@AustinBuchanan: Post as an answer?
Joshua Grochow
<cc.complexity-theory><graph-theory><graph-algorithms><complexity-classes>
Complexity of unique coloring of graphs
Andras Farago
# Complexity of unique coloring of graphs

(Asked by: username_0 on 2014-04-27)

The [Isolation lemma](http://en.wikipedia.org/wiki/Isolation_lemma) of Mulmuley, Vazirani, and Vazirani can be used to show that certain $\mathsf{NP}$-complete problems can be reduced via randomized polytime reductions to the *unique* solution version of the problem. This hints that the promise of a unique solution is not likely to make the problem significantly easier.

A specific example for such a reduction in the Mulmuley, Vazirani, and Vazirani paper [(pdf)](http://cs.berkeley.edu/~vazirani/pubs/matching.pdf)
is that CLIQUE can be reduced to UNIQUE CLIQUE via randomized polynomial time reductions. In this sense, UNIQUE CLIQUE is (almost) as hard as CLIQUE.

> Is there anything similar known about the UNIQUE $k$-COLORABILITY of graphs?

It is worth noting that the promise of unique colorability seems to involve more structural consequences than the uniqueness of the maximum clique.

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, complexity-classes

> **Comments:**
> **username_1**: http://www.sciencedirect.com/science/article/pii/S030439750400115X  
> **username_0**: Thank you, the linked paper provides an interesting answer.  
> **username_2**: @AndrasFarago From the reference so $PLAN-3-COL$ problems are essentially to distinguish $3$ colorability from $4$ colorability since we have a parsimonious reduction?  
> **username_3**: @AustinBuchanan: Post as an answer?  

---

## 1 answers

### Answer by username_1 on 2021-04-21. Score: 3 | Accepted answer

This [paper by Régis Barbanchon](https://www.sciencedirect.com/science/article/pii/S030439750400115X) might be of interest. From the abstract:

> We prove that the Satisfiability (resp. planar Satisfiability) problem
> is parsimoniously P-time reducible to the 3-Colorability (resp. Planar
> 3-Colorability) problem, that means that the exact number of solutions
> is preserved by the reduction, provided that 3-colorings are counted
> modulo their six trivial color permutations. In particular, the
> uniqueness of solutions is preserved, which implies that Unique
> 3-Colorability is exactly as hard as Unique Satisfiability in the
> general case as well as in the planar case...


---

