Graph class with easy chromatic number, but NP-hard coloring

Question

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?

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