1. Construction

2. Iterated Mycielskians

3. Properties

4. Cones over graphs

5. References

6. External links

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 {{harvs|first=Jan|last=Mycielski|authorlink=Jan Mycielski|year=1955|txt}}. 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

Let the n vertices of the given graph G be v₁, v₂, . . . , v_n. The Mycielski graph μ(G) contains G itself as a subgraph, together with n+1 additional vertices: a vertex u_i corresponding to each vertex v_i of G, and an extra 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.

The only new triangles in μ(G) are of the form v_iv_ju_k, where v_iv_jv_k is a triangle in G. Thus, if G is triangle-free, so is μ(G).

To see that the construction increases the chromatic number , consider a proper k-coloring of ; that is, a mapping with for adjacent vertices x,y. If we had for all i, then we could define a proper (k−1)-coloring of G by when , and otherwise. But this is impossible for , so c must use all k colors for , and any proper coloring of the last vertex w must use an extra color. That is, .

Iterated Mycielskians

Applying the Mycielskian repeatedly, starting with the one-edge graph, produces a sequence of graphs M_i = μ(M_i−1), 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 M₄ with 11 vertices and 20 edges.

In general, the graph M_i is triangle-free, (i−1)-vertex-connected, and i-chromatic. The number of vertices in M_i for i ≥ 2 is 3 × 2ⁱ⁻² − 1 {{OEIS|id=A083329}}, while the number of edges for i = 2, 3, . . . is:

1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, ... {{OEIS|id=A122695}}.

Properties

• If G has chromatic number k, then μ(G) has chromatic number k + 1 {{harv|Mycielski|1955}}.
• If G is triangle-free, then so is μ(G) {{harv|Mycielski|1955}}.
• More generally, if G has clique number ω(G), then μ(G) has clique number max(2,ω(G)).{{harv|Mycielski|1955}}.
• If G is a factor-critical graph, then so is μ(G) {{harv|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) {{harv|Fisher|McKenna|Boyer|1998}}.
• If G has domination number γ(G), then μ(G) has domination number γ(G)+1. {{harv|Fisher|McKenna|Boyer|1998}}.

Cones over graphs

A generalization of the Mycielskian, called a cone over a graph, was introduced by {{harvtxt|Stiebitz|1985}} and further studied by {{harvtxt|Tardif|2001}} and {{harvtxt|Lin|Wu|Lam|Gu|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 non-loop end of the path. The Mycielskian itself can be formed in this way as μ(G) = Δ₂(G).

While the cone construction does not always increase the chromatic number, {{harvtxt|Stiebitz|1985}} proved that it does so when applied iteratively to K₂. That is, define a sequence of families of graphs, called generalized Mycielskians, as

ℳ(2) = {K₂} 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 i ≥ r, 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

• {{citation

• {{citation

• {{citation

• {{citation

• {{citation

• {{citation

• {{citation

External links

• {{mathworld | title = Mycielski Graph | urlname = MycielskiGraph}}

• Cloud About Mercury
• Cloud Aerosol Transport System
• Cloud analytics
• Cloud Application Management for Platforms
• Cloud arch
• Cloud Arch
• Cloud architecture
• Cloud Atlas (2012 film)
• Cloud atlas (film)
• Cloud Atlas (film)
• Cloud Backup
• Cloud-based
• Cloud-based computing
• Cloud-based design and manufacturing
• Cloud-Based Design and Manufacturing
• Cloud-based integration
• Cloud Based Integration
• Cloud-based lending
• Cloud-based simulation
• Cloud based storage
• Cloudbaser
• Cloudbaser trike
• Cloudbaser Trikes Cloudbaser
• CloudBees
• Cloudberry Jam