Can we get a graph not containing $K_n$ with $\chi(G)\geq n$

61 Views Asked by At

It is known that the chromatic number of a complete graph is equal to the number of its vertices, that is $\chi(K_n)=n$. My question is can we get a graph $G$ not containing $K_n$ but with $\chi(G)\geq n$, for $n\geq 3$?

1

There are 1 best solutions below

2
On

Consider the graphs $M_n$ formed by iterating the Mycielskian operation, where $M_1$ is the one-vertex graph. All these graphs are triangle-free, hence $K_n$-free for $n\ge3$, and $\chi(M_n)=n$. Thus for any fixed $n\ge3$, $M_n$ is a graph with the desired property: $K_n$-free but requiring at least $n$ colours. Furthermore, all graphs $M_k$ with $k>n$ also have the desired property.