 Mycielski graph

A Mycielski graph commonly means a member of the family obtained by repeatedly applying the Mycielski construction to $K_2$. Writing $M_2=K_2$ and $M_{k+1}=\mu (M_k)$, its chromatic number is $k$, although it has no triangle. More broadly, the term is sometimes used for a graph produced by that construction from another starting graph; the chosen family convention should be stated.

The first examples are $M_2=K_2$, $M_3=C_5$, and the eleven-vertex $M_4$. Each construction adds a shadow for every old vertex and one apex, so the vertex counts satisfy $n_{k+1}=2n_k+1$. Hence $n_k=3\cdot 2^{k-2}-1$.

These graphs demonstrate that forbidding triangles in a graph does not bound the number of colors needed. A large clique is only one obstruction to coloring: constraints spread through a triangle-free graph can force arbitrarily large chromatic number.