= Triangle-free graphs with arbitrarily large chromatic number
{title2=$\chi(M_k)=k$}
Define $M_2=K_2$ and $M_{k+1}=\mu(M_k)$ for $k\geq2$. By the <Mycielskian chromatic increase> and <Mycielskian triangle preservation>, each $M_k$ is a finite <triangle-free graph> with <chromatic number> $k$. The first steps are $K_2,C_5$, the <Grötzsch graph>, and then a 23-<vertex> <graph> needing five colours. The <vertex> recurrence $n_{k+1}=2n_k+1$ gives $n_k=3\cdot2^{k-2}-1$. These explicit examples show how arbitrarily strong <graph coloring> constraints can accumulate without any three-<vertex> <clique>.
Back to article page
