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

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

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

Hamiltonian cycle in M4 (Grötzsch graph)

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

References

External links

This article is issued from Wikipedia - version of the Thursday, July 17, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.