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

Properties[edit]

Hamiltonian cycle in M4 (Grötzsch graph)

Cones over graphs[edit]

A generalized Mycielskian, formed as a cone over the 5-cycle, Δ3(C5) = Δ32(K2)).

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

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 K2. That is, define a sequence of families of graphs, called generalized Mycielskians, as

ℳ(2) = {K2} 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 ir, 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.

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