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:
en.wikipedia.o...
mathworld.wolf...
web.math.ucsb.e...
Recommended Books:
******************************* Hypergraph Theory *******************************
"Hypergraph Theory: An Introduction": amzn.to/48WKqfy
******************************* Graph Theory *******************************
"Introduction to Graph Theory (Trudeau)": amzn.to/48ZWhtj
"Graph Theory (Diestel)": amzn.to/4aYCSdW
******************************* Misc. Undergraduate Mathematics *******************************
Discrete Mathematics with Applications (Epp): amzn.to/4aWC1dM
A Book of Abstract Algebra (Pinter): amzn.to/3S2QmfV
Language, Proof and Logic: amzn.to/47EIZkE
Linear Algebra and Its Applications: amzn.to/48QsoMt
All the Math You Missed: amzn.to/3u5dORP
These are my Amazon Affiliate links. As an Amazon Associate I may earn commissions for purchases made through the links above.

[@soup_is_good_food5743]

Great job! Very clear and easy to follow, yet covering the essential points precisely. Thank you, I appreciate your work.

[@jj-wp8dt]

Such an amazing explanation. Thank you

[@VitalSine]

Thanks for watching! If you have any questions or suggestions, please let me know in the comments. If you'd like to see any concepts covered in the future, feel free to post them in the comments as well 👍

[@drlekshmirs-psgct3578]

Thanks. Add more videos on the properties of Mycielski graphs. Also on generalized Mycielskians.

[@VitalSine]

Hello. Thank you for the suggestions. I will make sure to create some new videos on the properties of Mycielski graphs and generalized Mycielskians.

[@kettonger]

Great explanation! Very easy to follow :D

[@VitalSine]

Thank you!

[@TheMitPitt]

Very neat, thanks

[@shanthikk]

Nice explanation sir..thank you 🙏🙏

[@VitalSine]

You're very welcome 👍

[@nagamaruthi8628]

Thank you for the explanation. Can you please explain its applications also. This extension of graph is very interesting

[@VitalSine]

Will do soon, thanks for the suggestion!

[@ugashinipreethi2620]

Please do videos on Properties of Mycielski graphs.

[@VitalSine]

Thanks for the suggestion, I will make some videos on properties of Mycielski graphs 🙂

[@ugashinipreethi2620]

@@VitalSine thankyou so much✨😊

[@jakesteele4047]

Please God just give me my math minor and engineering degree