What are Mycielski Graphs? [Discrete Mathematics]

What are Mycielski graphs and what is the Mycielski Construction in graph theory? This video will teach you about Mycielski graphs and what the Mycielski construction is.

The Mycielski Construction, or Mycielskian, is a unary graph operation. It is also known as the Mycielski graph of a graph. The Mycielskian of an undirected graph G, is itself an undirected graph with chromatic number one greater than its original graph. If a graph G has n vertices and m edges, the Mycielski graph has 3m + n edges and 2n +1 vertices. Its vertex set includes all vertices of the original graph, as well as an additional vertex corresponding to each vertex in the original graph, and one final additional vertex. It contains within itself a copy of the original graph. If the original graph is triangle-free, the Mycielski graph is also triangle-free.

Why is the Mycielski construction significant? For one, it lets us prove the interesting result that there exist triangle-free graphs of arbitrarily high chromatic number. Here are some links for more information:

https://en.wikipedia.org/wiki/Myciels...
https://mathworld.wolfram.com/Myciels...
http://web.math.ucsb.edu/~padraic/ucs...

Recommended Books:
******************************* Hypergraph Theory *******************************
"Hypergraph Theory: An Introduction": https://amzn.to/48WKqfy

******************************* Graph Theory *******************************
"Introduction to Graph Theory (Trudeau)": https://amzn.to/48ZWhtj

"Graph Theory (Diestel)": https://amzn.to/4aYCSdW

******************************* Misc. Undergraduate Mathematics *******************************
Discrete Mathematics with Applications (Epp): https://amzn.to/4aWC1dM

A Book of Abstract Algebra (Pinter): https://amzn.to/3S2QmfV

Language, Proof and Logic: https://amzn.to/47EIZkE

Linear Algebra and Its Applications: https://amzn.to/48QsoMt

All the Math You Missed: https://amzn.to/3u5dORP

These are my Amazon Affiliate links. As an Amazon Associate I may earn commissions for purchases made through the links above.