<p>I think you need to specify more carefully what you mean by "NP-hard" for a problem like this with a known solution but an unknown witness.</p>

<p>The most natural definition, to me, would be something like a many-one reduction, where there exist two polynomial time functions $p$ and $q$, where $p$ maps SAT instances to graphs with a known chromatic number and $q$ maps colorings of these graphs to truth values, such that $q(\chi)$ equals the correct truth value for SAT instance $X$ whenever $\chi$ is a valid optimal coloring of $p(X)$. However, this is not possible unless $\mathsf{NP}=\mathsf{coNP}$. For, if such $p$ and $q$ existed, then every unsatisfiable SAT instance $X$ would have a witness to its unsatisfiability, namely a coloring of $p(X)$.</p>

CC BY-SA 3.0
2016-02-06T01:10:25.070Z
2016-02-06T01:10:25.070Z
David Eppstein
<p>Is there a graph class for which the chromatic number can be computed in polynomial time, but finding an actual $k$-coloring with $k=\chi(G)$ is NP-hard?</p>

<p>Without any further restriction the answer would be yes. For example, it is known that in the class of 3-chromatic graphs it is still NP-hard to find a 3-coloring, while the chromatic number is trivial: it is 3, by definition.  </p>

<p>The above example, however, could be called "cheating" in a sense, because it makes the chromatic number easy by shifting the hardness to the definition of the graph class. Therefore, I think, the right question is this:</p>

<p>Is there a graph class that can be recognized in polynomial time, and the chromatic number of any graph $G$  in this class can also be computed in polynomial time, yet finding an actual $k=\chi(G)$-coloring for $G$ is NP-hard?</p>

CC BY-SA 3.0
2016-02-07T07:54:31.677Z
The definition of NP-hard is murky here, but it's not hard to argue that the existence of a (weakly) parsimonious Levin reduction from SAT to k-coloring implies that it's at least PPAD-hard. Proof sketch: Take a Nash Equilibrium instance and use a weakly parsimonious Levin reduction to SAT and then to k-coloring. Instances are recognizable because you can test if applying the two inverse mappings gives a valid NE instance. I don't know that the premise is true, however, although there at least do exist such weak parsimonious reductions. (Weakly here meaning "up to permutation of the colors")
Yonatan N
<cc.complexity-theory><graph-theory><graph-algorithms><np-hardness>
Graph class with easy chromatic number, but NP-hard coloring
Andras Farago
# Graph class with easy chromatic number, but NP-hard coloring

(Asked by: username_0 on 2016-02-05)

Is there a graph class for which the chromatic number can be computed in polynomial time, but finding an actual $k$-coloring with $k=\chi(G)$ is NP-hard?

Without any further restriction the answer would be yes. For example, it is known that in the class of 3-chromatic graphs it is still NP-hard to find a 3-coloring, while the chromatic number is trivial: it is 3, by definition.

The above example, however, could be called "cheating" in a sense, because it makes the chromatic number easy by shifting the hardness to the definition of the graph class. Therefore, I think, the right question is this:

Is there a graph class that can be recognized in polynomial time, and the chromatic number of any graph $G$ in this class can also be computed in polynomial time, yet finding an actual $k=\chi(G)$-coloring for $G$ is NP-hard?

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

> **Comments:**
> **username_1**: The definition of NP-hard is murky here, but it's not hard to argue that the existence of a (weakly) parsimonious Levin reduction from SAT to k-coloring implies that it's at least PPAD-hard. Proof sketch: Take a Nash Equilibrium instance and use a weakly parsimonious Levin reduction to SAT and then to k-coloring. Instances are recognizable because you can test if applying the two inverse mappings gives a valid NE instance. I don't know that the premise is true, however, although there at least do exist such weak parsimonious reductions. (Weakly here meaning "up to permutation of the colors")  

---

## 1 answers

### Answer by username_2 on 2016-02-06. Score: 5

I think you need to specify more carefully what you mean by "NP-hard" for a problem like this with a known solution but an unknown witness.

The most natural definition, to me, would be something like a many-one reduction, where there exist two polynomial time functions $p$ and $q$, where $p$ maps SAT instances to graphs with a known chromatic number and $q$ maps colorings of these graphs to truth values, such that $q(\chi)$ equals the correct truth value for SAT instance $X$ whenever $\chi$ is a valid optimal coloring of $p(X)$. However, this is not possible unless $\mathsf{NP}=\mathsf{coNP}$. For, if such $p$ and $q$ existed, then every unsatisfiable SAT instance $X$ would have a witness to its unsatisfiability, namely a coloring of $p(X)$.


---

