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.
Let the n vertices of the given graph G be v0, v1, etc. The Mycielski graph μ(G) 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
- 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 Mi 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 Δ2(G).
- Chvátal, Vašek (1974), "The minimality of the Mycielski graph", Graphs and Combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973), Lecture Notes in Mathematics 406, Springer-Verlag, pp. 243–246.
- Došlić, Tomislav (2005), "Mycielskians and matchings", Discussiones Mathematicae Graph Theory 25 (3).
- Fisher, David C.; McKenna, Patricia A.; Boyer, Elizabeth D. (1998), "Hamiltonicity, diameter, domination, packing, and biclique partitions of Mycielski's graphs", Discrete Applied Mathematics 84 (1–3): 93–105, doi:10.1016/S0166-218X(97)00126-1.
- Lin, Wensong; Wu, Jianzhuan; Lam, Peter Che Bor; Gu, Guohua (2006), "Several parameters of generalized Mycielskians", Discrete Applied Mathematics 154 (8): 1173–1182, doi:10.1016/j.dam.2005.11.001.
- Mycielski, Jan (1955), "Sur le coloriage des graphes", Colloq. Math. 3: 161–162.
- Stiebitz, M. (1985), Beiträge zur Theorie der färbungskritschen Graphen, Habilitation thesis, Technische Universität Ilmenau. As cited by Tardif (2001).
- Tardif, C. (2001), "Fractional chromatic numbers of cones over graphs", Journal of Graph Theory 38 (2): 87–94, doi:10.1002/jgt.1025.