Mycielskian

From Wikipedia, the free encyclopedia

In the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph G is a graph μ(G) formed from G by a construction of Jan Mycielski (1955), who used it to show that there exist triangle-free graphs with arbitrarily large chromatic number.

A generalized version of this construction has been studied by Lin et al (2006).

1 The construction
2 Example
3 Iterated Mycielskians
4 Properties
5 References
6 External links

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

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

[edit] Iterated Mycielskians

Applying the Mycielskian repeatedly, starting with the null graph, 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 null graph, the graph M₁ with one vertex and no edges, 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).

[edit] Properties

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).
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 is has a Hamiltonian cycle, then so does μ(G) (Fisher et al 1998).

[edit] 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), 243–246, Berlin: Lecture Notes in Mathematics, Vol. 406, Springer-Verlag.

Došlić, Tomislav (2005). "Mycielskians and matchings". Discuss. Math. Graph Theory 25 (3): 261–266.

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.

Lin, Wensong; Wu, Jianzhuan; Lam, Peter Che Bor; Gu, Guohua (2006). "Several parameters of generalized Mycielskians". Discrete Applied Mathematics 154 (8): 1173–1182.