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 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.




Contents






  • 1 Construction


  • 2 Iterated Mycielskians


  • 3 Properties


  • 4 Cones over graphs


  • 5 References


  • 6 External links





Construction




Mycielskian construction applied to a 5-cycle graph, producing the Grötzsch graph with 11 vertices and 20 edges, the smallest triangle-free 4-chromatic graph (Chvátal 1974).


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}{displaystyle chi (G)=k}, consider a proper k-coloring of μ(G)−{w}{displaystyle mu (G){-}{w}}{displaystyle mu (G){-}{w}}; that is, a mapping c:{v1,…,vn,u1,…,un}→{1,2,…,k}{displaystyle c:{v_{1},ldots ,v_{n},u_{1},ldots ,u_{n}}to {1,2,ldots ,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)}{displaystyle c(x)neq c(y)} for adjacent vertices x,y. If we had c(ui)⊂{1,2,…,k−1}{displaystyle c(u_{i})subset {1,2,ldots ,k{-}1}}{displaystyle c(u_{i})subset {1,2,ldots ,k{-}1}} for all i, then we could define a proper (k−1)-coloring of G by c′(vi)=c(ui){displaystyle c'!(v_{i})=c(u_{i})}{displaystyle c'!(v_{i})=c(u_{i})} when c(vi)=k{displaystyle c(v_{i})=k}{displaystyle c(v_{i})=k}, and c′(vi)=c(vi){displaystyle 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}{displaystyle chi (G)=k}, so c must use all k colors for {u1,…,un}{displaystyle {u_{1},ldots ,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}{displaystyle chi (mu (G))=k{+}1}.



Iterated Mycielskians





M2, M3 and M4 Mycielski graphs


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, 3, . . . is:


1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, ... (sequence A122695 in the OEIS).


Properties




Hamiltonian cycle in M4 (Grötzsch graph)



  • 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 max(2,ω(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




A generalized Mycielskian, formed as a cone over the 5-cycle, Δ3(C5) = Δ3(Δ2(K2)).


A generalization of the Mycielskian, called a cone over a graph, was introduced by Stiebitz (1985) and further studied by Tardif (2001) and Lin et al. (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) = Δ2(G).


While the cone construction does not always increase the chromatic number, Stiebitz (1985) proved that it does so when applied iteratively to K2. That is, define a sequence of families of graphs, called generalized Mycielskians, as


ℳ(2) = {K2} 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




  • Chvátal, Vašek (1974), "The minimality of the Mycielski graph", Graphs and Combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973), Lecture Notes in Mathematics, 406, Springer-Verlag, pp. 243–246.mw-parser-output cite.citation{font-style:inherit}.mw-parser-output q{quotes:"""""""'""'"}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-limited a,.mw-parser-output .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}.


  • Došlić, Tomislav (2005), "Mycielskians and matchings", Discussiones Mathematicae Graph Theory, 25 (3): 261–266, doi:10.7151/dmgt.1279, MR 2232992.


  • 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, doi:10.1016/S0166-218X(97)00126-1.


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


  • Mycielski, Jan (1955), "Sur le coloriage des graphes" (PDF), Colloq. Math., 3: 161–162.


  • Stiebitz, M. (1985), Beiträge zur Theorie der färbungskritschen Graphen, Habilitation thesis, Technische Universität Ilmenau. As cited by Tardif (2001).


  • Tardif, C. (2001), "Fractional chromatic numbers of cones over graphs", Journal of Graph Theory, 38 (2): 87–94, doi:10.1002/jgt.1025.



External links


  • Weisstein, Eric W. "Mycielski Graph". MathWorld.



-

Popular posts from this blog

Westermarck effect

Image
This article includes a list of references, but its sources remain unclear because it has insufficient inline citations . Please help to improve this article by introducing more precise citations. (November 2014) (Learn how and when to remove this template message) The Westermarck effect , or reverse sexual imprinting, is a hypothetical psychological effect through which people who live in close domestic proximity during the first few years of their lives become desensitized to sexual attraction. This phenomenon was first hypothesized by Finnish anthropologist Edvard Westermarck in his book The History of Human Marriage (1891) as one explanation for the incest taboo. Observations interpreted as evidence for the Westermarck effect have since been made in many places and cultures, including in the Israeli kibbutz system, and the Chinese Shim-pua marriage customs, as well as in biologically-related families. In the case of the Israeli kibbutzim (collective farms), children...
Read more

Orthodox Church in America

Image
For other uses, see Orthodox Church in America (disambiguation). Orthodox Church in America Recognition Autocephaly recognized by the Russian (since 1970), Bulgarian, Georgian, Polish, and Czech and Slovak Churches [1] Primate Metropolitan Tikhon (Mollard) [2] Headquarters Oyster Bay Cove, New York, United States Territory United States, Canada Possessions Mexico, formerly Australia and South America Language English, Church Slavonic, Spanish, Russian, Arabic, Koine Greek, Romanian, Bulgarian, Albanian Members 1 million adherents, [3] 90,000 (U.S. only) [a] [5] Bishops 14 [5] Parishes 700 [5] Monasteries 20 [5] Website oca.org Part of a series on the Eastern Orthodox Church Mosaic of Christ Pantocrator, Hagia Sophia Overview Structure Theology (History of theology) Liturgy Church history Holy Mysteries View of salvation View of Mary View of icons Background Crucifixion / Resurrection / Asc...
Read more

Italian cuisine

Image
"Italian restaurant" redirects here. For the television series, see Italian Restaurant. Some typical Italian gastronomic products in a window display in Imola Pizza is one of the world's most popular foods and a common fast food item Part of a series on the Culture of Italy History People Languages Traditions Mythology and folklore Mythology folklore Cuisine Festivals Religion Art Literature Music and performing arts Music Media Television Cinema Sport Monuments World Heritage Sites Symbols Flag Coat of arms Italy portal v t e Italian cuisine History Ancient Roman cuisine Medieval cuisine Early modern cuisine Contemporary cuisine Regional cuisines Apulian cuisine Lombard cuisine Neapolitan cuisine Roman cuisine Sicilian cuisine Venetian cuisine Cuisine of Abruzzo Cuisine of Sardinia Lists Chefs Dishes Pas...
Read more