Graph not $k$-colorable, without $k$-cliques

Question

I am looking for a simple example of a graph without $k$-cliques that is not $k$-colorable. $k=3$ would be great but perhaps a larger $k$ is required for this to be possible?

Answer 1

The Grotzsch graph is the smallest example of a triangle-free graph with chromatic number $4$. It is the Mycelskian of $C_5$. By considering the Mycelskian of the Grotzsch graph you have a triangle-free graph with $23$ vertices and chromatic number $5$. This procedure can be iterated.

I would point out some fancy ways for proving that there are triangle-free graphs with arbitrary chromatic number: for instance the existence of an infinite triangle-free difference graph with chromatic number $+\infty$, namely the graph whose vertices are the elements of $\mathbb{Z}$ and whose arcs join integers which differ by a cube.