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.

Construction

The Grötzsch graph as the Mycielskian of a 5-cycle graph.

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

M₂, M₃ and M₄ Mycielski graphs

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 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 OEIS).

Properties

Hamiltonian cycle in M₄ (Grötzsch graph)

• 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).

References

• 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" (PDF), 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.

External links

• Weisstein, Eric W., "Mycielski Graph", MathWorld.