Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
What is the smallest $n$ you can easily find an example for? – Hagen von Eitzen Nov 14 '12 at 16:19
$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$ – user45814 Nov 14 '12 at 16:53
up vote 1 down vote accepted

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.

share|cite|improve this answer
Oh, I see you found that by yourself in a comment meanwhile. – Hagen von Eitzen Nov 14 '12 at 17:05
Yes, but couldn't find a way to show it was minimal. Thanks! – user45814 Nov 14 '12 at 17:13
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) – user45814 Nov 14 '12 at 17:44
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$. – Hagen von Eitzen Nov 14 '12 at 17:50

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.