@MISC{DILWORTH.MIZ,
  AUTHOR = {Rudnicki, Piotr and Stewart, Lorna},
  TITLE = {The {M}ycielskian of a Graph},
  NOTE = {This work has been partially supported by the NSERC grant
      OGP 9207.},
  SECTION1 = {Preliminaries},
  SECTION2 = {Partitions},
  SECTION3 = {Chromatic number and clique cover number},
  SECTION4 = {Complement},
  SECTION5 = {Adjacent set},
  SECTION6 = {Natural numbers as vertices},
  SECTION7 = {Mycielskian of a graph},
  DAY = {2},
  MONTH = {July},
  YEAR = {2010},
  ADDRESS1 = {Department of Computing Science\\University of Alberta\\Edmonton, AB, Canada},
  ADDRESS2 = {Department of Computing Science\\University of Alberta\\Edmonton, AB, Canada},
  SUMMARY = {Let $\omega(G)$ and $\chi(G)$ be the clique number and the chromatic
  number of a graph $G$. Mycielski~\cite{Mycielski55} presented a
  construction that for any $n$ creates a graph $M_n$  which is triangle-free
  ($\omega(G) = 2$) with $\chi(G) > n$.  The starting point is the complete
  graph of two vertices ($K_2$).  $M_(n+1)$ is obtained from $M_n$
  through the operation $\mu(G)$ called the Mycielskian of a graph $G$.
  \par
  We first define the operation $\mu(G)$ and then show that
  $\omega(\mu(G)) = \omega(G)$ and $\chi(\mu(G)) = \chi(G)+1$.  This is
  done for arbitrary graph $G$, see also~\cite{LUP95}.  Then we
  define the sequence of graphs $M_n$ each of exponential size in $n$
  and give their clique and chromatic numbers.}}

@article{Mycielski55,
 author     = {J. Mycielski},
 title      = {Sur le coloriage des graphes},
 journal    = {Colloquium Mathematicum},
 volume     = {3},
 year       = {1955},
 pages      = {161-162}}

@article{LUP95,
  author    = {M. Larsen and J. Propp and D. Ullman},
  title     = {The fractional chromatic number of {M}ycielski's graphs},
  journal   = {Journal of Graph Theory},
  volume    = {19},
  year      = {1995},
  pages     = {411-416}}
