%0 Journal Article
%T The Mycielskian of a Graph
%A Piotr Rudnicki
%A Lorna Stewart
%J Formalized Mathematics
%@ 1898-9934
%D 2011
%I 
%R 10.2478/v10037-011-0005-6
%X 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 Mn which is triangle-free (¦Ø(G) = 2) with ¦Ö(G) > n. The starting point is the complete graph of two vertices (K2). M(n+1) is obtained from Mn 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 Mn each of exponential size in n and give their clique and chromatic numbers.
%U http://versita.metapress.com/content/k67621j857056460/?p=25816f9e6d274cf5ab90abc2a2c39abd&pi=4