So I need to find the smallest imperfect graph, $G$ who's chromatic number equals it's clique number. ie:
$$\chi(G) = \omega(G)$$
Finding imperfect graphs isn't hard (since finding perfect graphs is). Even finding imperfect graphs with this property isn't too hard. But how do we find the smallest graph (I assume minimal # vertices). Even if I have an idea what this graph is, how can I prove it is the smallest? I.e if I think sum graph on $n$ vertices is the smallest graph satisfying this, it seems daunting to show every graph of order $<n$ fails to satisfy this (unless $n$ is relatively small).
Methods to approach and tackle this problem?