The Mycielskian of a Graph

Let ω(G) and χ(G) be the clique number and the chromatic number of a graph G. Mycielski [11] presented a construction that for any n creates a graph M_n which is triangle-free (ω(G) = 2) with χ(G) > n. The starting point is the complete graph of two vertices (K₂). M(_n+1) is obtained from M_n through the operation μ(G) called the Mycielskian of a graph G.

We first define the operation μ(G) and then show that ω(μ(G)) = ω(G) and χ(μ(G)) = χ(G) + 1. This is done for arbitrary graph G, see also [10]. Then we define the sequence of graphs M_n each of exponential size in n and give their clique and chromatic numbers.