Mycielskis

Mycielskis are a class of graphs with a special property related to chromatic number. A graph G is called a Mycielski graph if it can be constructed from a smaller graph using a specific operation. This operation, known as the Mycielski construction, increases the chromatic number of the graph by one while keeping the graph triangle-free. 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 starts with a graph G. If G has vertices v1, v2, ..., vn, the Mycielski graph M(G) is formed by creating n new vertices u1, u2, ..., un, one for each vertex in G. Additionally, a new vertex w is added. For each edge (vi, vj) in G, edges are added in M(G) between ui and uj, and also between ui and vk for all k such that (vi, vk) is an edge in G. The new vertex w is connected to all the ui vertices.

A notable example is the Grötzsch graph, which is the Mycielski graph of a 5-cycle. The Grötzsch graph has a chromatic number of 4 and is triangle-free. This demonstrates that it is possible to have triangle-free graphs with arbitrarily high chromatic numbers, a result that contrasts with the fact that any graph with chromatic number k must contain a k-clique if it is dense enough. Mycielski graphs provide a way to construct such graphs.