Mycielskian

In the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph is a larger graph formed from it by a construction of Jan Mycielski (1955).

The construction preserves the property of being triangle-free but increases the chromatic number; by applying the construction repeatedly to a triangle-free starting graph, Mycielski showed that there exist triangle-free graphs with arbitrarily large chromatic number.

The Mycielski graph μ(G) contains G itself as a subgraph, together with n+1 additional vertices: a vertex ui corresponding to each vertex vi of G, and an extra vertex w. Each vertex ui is connected by an edge to w, so that these vertices form a subgraph in the form of a star K1,n.

In addition, for each edge vivj of G, the Mycielski graph includes two edges, uivj and viuj.

Thus, if G has n vertices and m edges, μ(G) has 2n+1 vertices and 3m+n edges.

The only new triangles in μ(G) are of the form vivjuk, where vivjvk is a triangle in G. Thus, if G is triangle-free, so is μ(G).

To see that the construction increases the chromatic number

, and any proper coloring of the last vertex w must use an extra color.

χ ( μ (

Applying the Mycielskian repeatedly, starting with the one-edge graph, produces a sequence of graphs Mi = μ(Mi−1), sometimes called the Mycielski graphs.

The first few graphs in this sequence are the graph M2 = K2 with two vertices connected by an edge, the cycle graph M3 = C5, and the Grötzsch graph M4 with 11 vertices and 20 edges.

In general, the graph Mi is triangle-free, (i−1)-vertex-connected, and i-chromatic.

The number of vertices in Mi for i ≥ 2 is 3 × 2i−2 − 1 (sequence A083329 in the OEIS), while the number of edges for i = 2, 3, .

is: A generalization of the Mycielskian, called a cone over a graph, was introduced by Stiebitz (1985) and further studied by Tardif (2001) and Lin et al. (2006).

In this construction, one forms a graph

from a given graph G by taking the tensor product G × H, where H is a path of length i with a self-loop at one end, and then collapsing into a single supervertex all of the vertices associated with the vertex of H at the non-loop end of the path.

The Mycielskian itself can be formed in this way as μ(G) = Δ2(G).

While the cone construction does not always increase the chromatic number, Stiebitz (1985) proved that it does so when applied iteratively to K2.

That is, define a sequence of families of graphs, called generalized Mycielskians, as For example, ℳ(3) is the family of odd cycles.

Then each graph in ℳ(k) is k-chromatic.

The proof uses methods of topological combinatorics developed by László Lovász to compute the chromatic number of Kneser graphs.

The triangle-free property is then strengthened as follows: if one only applies the cone construction Δi for i ≥ r, then the resulting graph has odd girth at least 2r + 1, that is, it contains no odd cycles of length less than 2r + 1.

Thus generalized Mycielskians provide a simple construction of graphs with high chromatic number and high odd girth.