Graph coloring doesn't have certificate that smaller coloring doesn't exist in general.
I am looking for graph classes where finding explicit coloring is not polynomial and have polynomially verifiable certificate that it is minimum.
Example of such class might be graphs for which the clique number equals the chromatic number, i.e. $\omega(G)=\chi(G)$ and finding coloring is not polynomial. Find both coloring and clique and the clique will be certificate that smaller coloring doesn't exist because of the inequality $\omega(G) \le \chi(G)$.
Are there nice characterizations of such graph classes (preferably by forbidden induced subgraphs)?
Paper defines such graphs "weakly perfect" and claims that deciding $\omega(G)=\chi(G)$ is NP-complete.
Near misses are perfect and cobipartite but there the problems are polynomial.