Mycielskian

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

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

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.

Example[edit]

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

Iterated Mycielskians[edit]

M2, M3 and M4 Mycielski graphs

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

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

Properties[edit]

Hamiltonian cycle in M4 (Grötzsch graph)

Cones over graphs[edit]

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

References[edit]

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

External links[edit]