0
$\begingroup$

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 $ fails to satisfy this (unless $n$ is relatively small).

Methods to approach and tackle this problem?

  • 0
    $C_5$ with an added internal vertex connected to 3 vertices of $C_5$, 2 of which neighbours, 1 of which is not a neighbour to either. so $n=6$2012-11-14

1 Answers 1

1

Consider the cyclic graph with five vertices $a,b,c,d,e$ and add a sixth vertex $f$ with edges $af$, $bf$, $df$. Then $\omega(G)=\chi(G)=3$ and the graph is not perfect becaus the induced subgraph obtained by removing $f$ has $\chi=3$ and $\omega=2$.

Why is six minimal? For graphs up to four vertices, $\chi=\omega$ always holds, hence every graph with at most five vertices having $\chi=\omega$ is perfect.

  • 1
    If $\omega=n$, then trivially $\omega=\chi$. If $\omega=n-1$, then colour a maximal clique with $\omega$ colours and the remaining vertex with the colour of one of its non-neighbours. If $\omega\le n-2$, then $G$ is either $C_4$ or a tree with $\chi=2$ or disconnected with $\chi=1$.2012-11-14