Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Mycielskian
Summary
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.
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 , 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, .
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 , while the number of edges for i = 2, 3, . . . is:
1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, ... .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.