Mycielskian

Construction

Let the n vertices of the given graph G be v₀, v₁, etc. The Mycielski graph μ(G) of G contains G itself as an isomorphic subgraph, together with n+1 additional vertices: a vertex u_i corresponding to each vertex v_i of G, and another vertex w. Each vertex u_i is connected by an edge to w, so that these vertices form a subgraph in the form of a star K_1,n. In addition, for each edge v_iv_j of G, the Mycielski graph includes two edges, u_iv_j and v_iu_j.

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

Example

The illustration shows Mycielski's construction as applied to a 5-vertex cycle graph with vertices v_i for 0 ≤ i ≤ 4. The resulting Mycielskian is the Grötzsch graph, an 11-vertex graph with 20 edges. The Grötzsch graph is the smallest triangle-free 4-chromatic graph (Chvátal 1974).

Iterated Mycielskians

Applying the Mycielskian repeatedly, starting with a graph with a single edge, produces a sequence of graphs M_i = μ(M_i-1), also sometimes called the Mycielski graphs. The first few graphs in this sequence are the graph M₂ = K₂ with two vertices connected by an edge, the cycle graph M₃ = C₅, and the Grötzsch graph with 11 vertices and 20 edges.

In general, the graphs M_i in this sequence are triangle-free, (i-1)-vertex-connected, and i-chromatic. M_i has 3 × 2^i-2 - 1 vertices (sequence A083329 in the OEIS). The numbers of edges in M_i, for small i, are

0, 0, 1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, ... (sequence A122695 in the OEIS).

Properties

If G has chromatic number k, then μ(G) has chromatic number k + 1 (Mycielski 1955).

If G is triangle-free, then so is μ(G) (Mycielski 1955).

More generally, if G has clique number ω(G), then μ(G) has clique number max(2,ω(G)).(Mycielski 1955).

If G is a factor-critical graph, then so is μ(G) (Došlić 2005). In particular, every graph M_i for i ≥ 2 is factor-critical.

If G has a Hamiltonian cycle, then so does μ(G) (Fisher, McKenna & Boyer 1998).

If G has domination number γ(G), then μ(G) has domination number γ(G)+1. (Fisher, McKenna & Boyer 1998).

Cones over graphs

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 Δ_i(G) from a given graph G by taking the tensor product of graphs 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 other end of the path from the self-loop. The Mycielskian itself can be formed in this way as Δ₂(G).

While it is not true in general that the cone construction increases the chromatic number, Stiebitz (1985) proved that this is true when one iteratively applies the construction to K₂. That is, define a sequence of families of graphs, called generalized Mycielskians, as

ℳ(2) = {K₂} and ℳ(k+1) = {Δ_i(G) | G ∈ ℳ(k), i ∈ ℕ}.

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.