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?
Graph class with easy chromatic number, but NP-hard coloring
cc.complexity theory;graph theory;graph algorithms;np hardness