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
Let the n vertices of the given graph G be v1, v2, . . . , vn. The Mycielski graph μ(G) contains G itself as a subgraph, together with n+1 additional vertices: a vertex ui corresponding to each vertex vi of G, and an extra 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. The only new triangles in μ(G) are of the form vivjuk, where vivjvk is a triangle in G. Thus, if G is triangle-free, so is μ(G). To see that the construction increases the chromatic number χ ( G ) = k {\displaystyle \chi (G)=k} , consider a proper k-coloring of μ ( G ) − { w } {\displaystyle \mu (G){-}\{w\}} ; that is, a mapping c : { v 1 , … , v n , u 1 , … , u n } → { 1 , 2 , … , k } {\displaystyle c:\{v_{1},\ldots ,v_{n},u_{1},\ldots ,u_{n}\}\to \{1,2,\ldots ,k\}} with c ( x ) ≠ c ( y ) {\displaystyle c(x)\neq c(y)} for adjacent vertices x,y. If we had c ( u i ) ∈ { 1 , 2 , … , k − 1 } {\displaystyle c(u_{i})\in \{1,2,\ldots ,k{-}1\}} for all i, then we could define a proper (k−1)-coloring of G by c ′ ( v i ) = c ( u i ) {\displaystyle c'\!(v_{i})=c(u_{i})} when c ( v i ) = k {\displaystyle c(v_{i})=k} , and c ′ ( v i ) = c ( v i ) {\displaystyle c'\!(v_{i})=c(v_{i})} otherwise. But this is impossible for χ ( G ) = k {\displaystyle \chi (G)=k} , so c must use all k colors for { u 1 , … , u n } {\displaystyle \{u_{1},\ldots ,u_{n}\}} , and any proper coloring of the last vertex w must use an extra color. That is, χ ( μ ( G ) ) = k + 1 {\displaystyle \chi (\mu (G))=k{+}1} .
Iterated Mycielskians
Applying the Mycielskian repeatedly, starting with the one-edge graph, produces a sequence of graphs Mi = μ(Mi−1), 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 M4 with 11 vertices and 20 edges. In general, the graph Mi is triangle-free, (i−1)-vertex-connected, and i-chromatic. The number of vertices in Mi for i ≥ 2 is 3 × 2i−2 − 1 (sequence A083329 in the OEIS), while the number of edges for i ≥ 2 is 1 2 ( 7 × 3 i − 2 + 1 ) − 3 × 2 i − 2 {\displaystyle {\frac {1}{2}}\left(7\times 3^{i-2}+1\right)-3\times 2^{i-2}} , which begins as:
1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, ... (sequence A122695 in the OEIS).
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). More generally, if G has clique number ω(G), then μ(G) has clique number of the maximum among 2 and ω(G). (Mycielski 1955) If G is a factor-critical graph, then so is μ(G) (Došlić 2005). In particular, every graph Mi for i ≥ 2 is factor-critical. If G has a Hamiltonian cycle, then so does μ(G) (Fisher, McKenna & Boyer 1998). If G has domination number γ(G), then μ(G) has domination number γ(G)+1 (Fisher, McKenna & Boyer 1998).
Cones over graphs
… excerpt ends here. Continue reading the full article.
