= Mycielski graph
{title2=$M_{k+1}=\mu(M_k)$}
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\cdot2^{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>.
Back to article page
