 Mycielskian

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 satisfiesand 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,\dots ,v_n\}$, with $n\ge 1$. Keep these vertices, add distinct Mycielski shadow vertices $u_1,\dots ,u_n$, and add a Mycielski apex $w$. The vertex set and complete list of edges areThere 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.^[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_1{v}_2$, abbreviating $\{v_1,v_2\}$. Its Mycielskian has exactly the edges $v_1{v}_2,u_1{v}_2,u_2{v}_1,w{u}_1,w{u}_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.

In mathematics and graph theory, a Mycielski graph, or Mycielski construction, is a method for constructing new graphs from existing ones. The Mycielski construction is used primarily to create triangle-free graphs, which are graphs that do not contain any cycles of length three (triangles). The construction works as follows: 1. **Start with a graph \( G \)**: This can be any simple graph.