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 . 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''_''i''''v''_''j'' of ''G'', the Mycielski graph includes two edges, ''u''_''i''''v''_''j'' and ''v''_''i''''u''_''j''.

Thus, if ''G'' has ''n'' vertices and ''m'' edges, μ(''G'') has 2''n''+1 vertices and 3''m''+''n'' edges.

The only new triangles in μ(''G'') are of the form ''v''_''i''''v''_''j''''u''_''k'', where ''v''_''i''''v''_''j''''v''_''k'' is a triangle in ''G''. Thus, if ''G'' is triangle-free, so is μ(''G'').

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

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^''i''−2 − 1 , while the number of edges for ''i'' = 2, 3, . . . is:

: 1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, ... .

Properties

*If ''G'' has chromatic number ''k'', then μ(''G'') has chromatic number ''k'' + 1 .
*If ''G'' is triangle-free, then so is μ(''G'') .
*More generally, if ''G'' has clique number ω(''G''), then μ(''G'') has clique number max(2,ω(''G'')) .
*If ''G'' is a factor-critical graph, then so is μ(''G'') . In particular, every graph ''M''_''i'' for ''i'' ≥ 2 is factor-critical.
*If ''G'' has a Hamiltonian cycle, then so does μ(''G'') .
*If ''G'' has domination number γ(''G''), then μ(''G'') has domination number γ(''G'')+1 .

Cones over graphs

A generalization of the Mycielskian, called a cone over a graph, was introduced by and further studied by and . 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, proved that it does so when applied iteratively to ''K''₂. That is, define a sequence of families of graphs, called generalized Mycielskians, as
: ℳ(2) = and ℳ(''k''+1) = .
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 2''r'' + 1, that is, it contains no odd cycles of length less than 2''r'' + 1.
Thus generalized Mycielskians provide a simple construction of graphs with high chromatic number and high odd girth.

References

*.
*.
*.
*.
*.
*. As cited by .
*.

External links

*{{mathworld , title = Mycielski Graph , urlname = MycielskiGraph

Graph operations