Mycielskian

Mycielskian is a term used in graph theory, a branch of mathematics that studies the properties and relationships of graphs, which are structures consisting of vertices (or nodes) connected by edges (or lines). The Mycielskian of a graph is a specific construction that produces a new graph from an existing one, increasing its chromatic number, which is the smallest number of colors needed to color the graph such that no two adjacent vertices share the same color. This construction was introduced by Stanisław Mycielski in 1955.

The Mycielskian of a graph G, denoted as M(G), is constructed as follows: start with a copy of G, then add a new vertex v and connect it to all vertices in G. Finally, for each edge (u, w) in G, add a new vertex and connect it to both u and w. This process effectively creates a new graph that is larger than G but has a higher chromatic number.

The Mycielskian construction is significant in graph theory because it provides a method to generate graphs with arbitrarily high chromatic numbers. This is useful in various areas of graph theory, including the study of graph coloring, graph minors, and the classification of graphs. Additionally, the Mycielskian construction has applications in computer science, particularly in the design and analysis of algorithms for graph problems.

The Mycielskian of a graph G is not unique; different choices of vertices and edges in the construction process can lead to different graphs. However, all Mycielskian graphs of G share the same chromatic number, which is one more than the chromatic number of G. This property makes the Mycielskian construction a valuable tool in the study of graph coloring and related topics.