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:
[ Ссылка ]
[ Ссылка ]
[ Ссылка ]
Recommended Books:
******************************** Hypergraph Theory ********************************
"Hypergraph Theory: An Introduction": [ Ссылка ]
******************************** Graph Theory ********************************
"Introduction to Graph Theory (Trudeau)": [ Ссылка ]
"Graph Theory (Diestel)": [ Ссылка ]
******************************** Misc. Undergraduate Mathematics ********************************
Discrete Mathematics with Applications (Epp): [ Ссылка ]
A Book of Abstract Algebra (Pinter): [ Ссылка ]
Language, Proof and Logic: [ Ссылка ]
Linear Algebra and Its Applications: [ Ссылка ]
All the Math You Missed: [ Ссылка ]
These are my Amazon Affiliate links. As an Amazon Associate I may earn commissions for purchases made through the links above.
