„Mycielski-konstrukció” változatai közötti eltérés

Ha a két csúcsból és egyetlen élből álló gráfból kiindulva ismételten alkalmazzuk a Mycielski-konstrukciót, gráfok ''M''_''i'' = M(''M''_{''i''−1−1}) sorozatát kapjuk, ezeket Mycielski-gráfoknak is nevezzük. A sorozat első néhány eleme az ''M''₂ = ''K''₂, ami két csúcsból és egy élből áll, az ''M''₃ = ''C''₅ [[körgráf]] és a 11 csúcsból és 20 élből álló [[Grötzsch-gráf]].

Általában véve a sorozat ''M''_''i'' gráfjairól elmondható, hogy [[háromszögmentes gráf|háromszögmentesek]], (''i''−1−1)-[[k-szorosan összefüggő gráf|szeresen összefüggőek]] és ''i''-[[kromatikus szám|kromatikusak]]. Az ''M''_''i'' csúcsainak száma 3 · 2^{''i''−2−2} −− 1{{OEIS|id=A083329}}. Az ''M''_''i'' éleinek számát (kis ''i''-kre) a következő sorozat adja:

A Mycielski-konstrukció egy általánosítása a gráf feletti kúp képzése, amit {{harvtxt|Stiebitz|1985}} vezetett be, majd {{harvtxt|Tardif|2001}} és {{harvtxt|Lin|Wu|Lam|Gu|2006}} tanulmányozták tovább. Ebben a konstrukcióban adott ''G'' gráfból úgy képezzük a Δ_''i''(''G'') gráfot, hogy vesszük a ''G'' ×× ''H'' [[Gráfok tenzorszorzata|tenzorszorzatot]], ahol ''H'' egy ''i'' hosszú út a végén egy hurokéllel, majd a hurokél ''H'' csúcsával kapcsolódó összes csúcsot egyetlen szupercsúccsá húzzuk össze. Maga a Mycielski-konstrukció ebben az általánosításban a Δ₂(''G'')-nek felel meg.