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
    What is the smallest $n$ you can easily find an example for?2012-11-14
  • 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.

  • 0
    Oh, I see you found that by yourself in a comment meanwhile.2012-11-14
  • 0
    Yes, but couldn't find a way to show it was minimal. Thanks!2012-11-14
  • 0
    Is there an easy way to show for graphs up to four verticies that X=w? I can tell it's true, but not sure if I can just state that (Ill post this as a new question, since it seems it may take some thought)2012-11-14
  • 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