Take the 2-minute tour ×

Is there a theorem that states if a graph has $\chi(G) = n$ then it also contains a subgraph isomorphic to $K_n$?

share|improve this question
You are trying to compare the chromatic number to the so called clique number. There is a whole literature about this problem. Google should provide relevant information. –  Mariano Suárez-Alvarez May 13 '13 at 22:25

2 Answers 2

The answer is simply NO, since there are triangle-free graphs with arbitrarily high chromatic number, in virtue of the following lemma:

If $G$ is a triangle-free graph with chromatic number $n$, its Mycelskian $M(G)$ is a triangle free graph with chromatic number $n+1$.

share|improve this answer

Consider the cycle on $5$ vertices.

share|improve this answer
Yes, $\chi(G)=3$ here but no $K_3$. –  coffeemath Jan 29 '13 at 11:56

Your Answer


