= Mycielskian
{c}
{title2=$\mu(G)$}
{wiki}
= Mycielski construction
{c}
{synonym}
The Mycielski construction replaces a graph $G$ with a graph $\mu(G)$ having one shadow vertex for each original vertex and one further vertex adjacent to every shadow. It satisfies
$$
\chi(\mu(G))=\chi(G)+1
$$
and preserves triangle-freeness. Iterating it from the five-cycle gives triangle-free graphs of arbitrarily large chromatic number.
Here $G$ is a finite <simple graph> with at least one <vertex>; it need not have an <edge>. The <Mycielskian> separates two ways of needing many colours: a large <clique> forces distinct colours immediately, but a <triangle-free graph> can impose incompatible choices through its whole pattern of <graph adjacency>. The <Mycielski construction> increases that global constraint while preserving the absence of <triangles in a graph>.
Write the <vertex set> of $G$ as $\{v_1,\ldots,v_n\}$, with $n\geq1$. Keep these <vertices>, add distinct <Mycielski shadow vertices> $u_1,\ldots,u_n$, and add a <Mycielski apex> $w$. The <vertex set> and complete list of <edges> are
$$
\begin{aligned}
V(\mu(G))&=\{v_1,\ldots,v_n,u_1,\ldots,u_n,w\},\\
E(\mu(G))&=E(G)\cup\{\{u_i,v_j\},\{u_j,v_i\}:\{v_i,v_j\}\in E(G)\}\cup\{\{w,u_i\}:1\leq i\leq n\}.
\end{aligned}
$$
There are no other <edges>: the <Mycielski shadow vertices> form an <independent set>, $w$ has no original <vertex> as a neighbour, and $u_i$ is not adjacent to $v_i$. Each <Mycielski shadow vertex> copies its original <vertex>'s <graph neighbourhood> within the original <vertex set>, not its position in the drawing. This is the construction in the inspected research paper.<Mycielski graphs and PR proofs by Emre Yolcu and others>[§4.1, manuscript pp. 5–6, construction steps 1–3]{ref}
For $n$ original <vertices> and $m$ original <edges>, direct counting gives $2n+1$ <vertices> and $3m+n$ <edges>. The original <vertices> induce a copy of $G$, so no original <graph adjacency> is lost. A drawing crossing is not an extra <vertex>.
Start with the <complete graph> $K_2$, whose only <edge> is $v_1v_2$, abbreviating $\{v_1,v_2\}$. Its <Mycielskian> has exactly the <edges> $v_1v_2,u_1v_2,u_2v_1,wu_1,wu_2$. Reading them as $v_1,v_2,u_1,w,u_2,v_1$ gives the <cycle graph> $C_5$. A <proper vertex colouring> gives $v_1,u_1$ colour 1, $v_2,u_2$ colour 2, and $w$ colour 3. Two colours cannot close an <odd cycle>, so its <chromatic number> is exactly three.
\Image[/mycielski-single-edge-five-cycle-colouring.png]
{title=The <Mycielski construction> turns the <complete graph> $K_2$ into the <cycle graph> $C_5$}
{description=Numbers inside the <vertices> are colours. Solid, dashed and dotted <edges> distinguish the original connection, copied neighbour constraints and <Mycielski apex> connections. The second drawing is a single <odd cycle>, with no <triangles in a graph>.}
Back to article page
