In the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph G is a graph μ(G) formed from G by a construction of Jan Mycielski (1955), who used it to show that there exist triangle-free graphs with arbitrarily large chromatic number.
Contents |
Let the n vertices of the given graph G be v0, v1, etc. The Mycielski graph of G contains G itself as an isomorphic subgraph, together with n+1 additional vertices: a vertex ui corresponding to each vertex vi of G, and another 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 illustration shows Mycielski's construction as applied to a 5-vertex cycle graph with vertices vi 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).
Applying the Mycielskian repeatedly, starting with a graph with a single edge, produces a sequence of graphs Mi = μ(Mi-1), also 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 with 11 vertices and 20 edges.
In general, the graphs Mi in this sequence are triangle-free, (i-1)-vertex-connected, and i-chromatic. Mi has 3 × 2i-2 - 1 vertices (sequence A083329 in OEIS). The numbers of edges in Mi, for small i, are
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 Δ2(G).