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". The Mycielski graph μ("G") contains "G" itself as a subgraph, together with "n"+1 additional vertices: a vertex "u" corresponding to  each vertex "v" of "G", and an extra vertex "w". Each vertex "u" is connected by an edge to "w", so that these vertices form a subgraph in the form of a star "K". In addition, for each edge "v""v" of "G", the Mycielski graph includes two edges, "u""v" and "v""u". 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""v""u", where "v""v""v" is a triangle in "G". Thus, if "G" is triangle-free, so is μ("G"). To see that the construction increases  the chromatic number formula_1, consider a proper "k"-coloring of formula_2; that is, a mapping formula_3 with formula_4 for adjacent vertices "x","y". If we had formula_5 for all "i", then we could define a proper ("k"−1)-coloring of "G" by formula_6 when formula_7, and formula_8 otherwise. But this is impossible for formula_1, so "c" must use all "k" colors for formula_10, and any proper coloring of the last vertex "w" must use an extra color. That is, formula_11. Iterated Mycielskians. Applying the Mycielskian repeatedly, starting with the one-edge graph, produces a sequence of graphs "M" = μ("M"), 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" is triangle-free, ("i"−1)-vertex-connected, and "i"-chromatic. The number of vertices in "M" for "i" ≥ 2 is 3 × 2 − 1 , while the number of edges for "i" = 2, 3, . . . is: 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 Δ("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 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 Δ 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.