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?

  • $\begingroup$ 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") $\endgroup$
    – Yonatan N
    Feb 7, 2016 at 7:54

1 Answer 1


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)$.


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.