Mycielski

Mycielski is a term that can refer to several related concepts, primarily in the fields of graph theory and mathematics. The most common association is with the Mycielski graph, also known as the Mycielskian.

The Mycielski graph, denoted as $M_n$, is a construction in graph theory that produces a triangle-free graph with a large chromatic number. A triangle is a complete graph on three vertices, denoted as $K_3$. The chromatic number of a graph is the minimum number of colors needed to color its vertices such that no two adjacent vertices share the same color. The Mycielski construction is notable because it allows for the creation of triangle-free graphs with arbitrarily high chromatic numbers. For example, $M_3$ is the Grötzsch graph, which is triangle-free and has a chromatic number of 4.

The construction of the Mycielski graph $M_{n+1}$ from a graph $M_n$ involves adding $2|V(M_n)| + 1$ new vertices. For each vertex $v$ in $M_n$, two new vertices are created. One of these new vertices is connected to all neighbors of $v$ in $M_n$. The second new vertex is connected to the first new vertex and to all neighbors of $v$. A final vertex is added and connected to all the other newly created vertices. This process iteratively builds larger and more complex triangle-free graphs.

The Mycielski graph is named after Polish mathematician Jan Mycielski, who introduced this construction in 1955. His work aimed to demonstrate that there exist triangle-free graphs with any prescribed chromatic number, a significant result in extremal graph theory. Beyond graph theory, the name "Mycielski" might also appear in other mathematical contexts, but the graph construction is its most recognized application.

---