Let the nvertices of the given graph G be v1, v2,..., vn. The Mycielski graph μ containsG 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 starK1,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, μ has 2n+1 vertices and 3m+n edges. The only new triangles in μ are of the form vivjuk, where vivjvk is a triangle in G. Thus, if G is triangle-free, so is μ. To see that the construction increases the chromatic number, consider a properk-coloring of ; that is, a mapping with for adjacent verticesx,y. If we had for all i, then we could define a proper -coloring of G by when , and otherwise. But this is impossible for, so c must use all kcolors for, and any proper coloring of the last vertex w must use an extra color. That is,.
Iterated Mycielskians
Applying the Mycielskian repeatedly, starting with the one-edge graph, produces a sequence of graphs Mi = μ, 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 graphM3 = C5, and the Grötzsch graphM4 with 11 vertices and 20 edges. In general, the graph Mi is triangle-free, -vertex-connected, and i-chromatic. The number of vertices in Mi for i ≥ 2 is 3 × 2i−2 − 1, while the number of edges for i = 2, 3,... is:
Properties
If G has chromatic number k, then μ has chromatic number k + 1.
If G is triangle-free, then so is μ.
More generally, if G has clique numberω, then μ has clique number max..
If G is a factor-critical graph, then so is μ. In particular, every graph Mi for i ≥ 2 is factor-critical.
A generalization of the Mycielskian, called a cone over a graph, was introduced by and further studied by and. In this construction, one forms a graph Δi from a given graph G by taking the tensor product of graphsG × 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 μ = Δ2. While the cone construction does not always increase the chromatic number, 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, ℳ is the family of odd cycles. Then each graph in ℳ 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.
