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

==Definíció==

A Mycielski-konstrukció a <math>V(G)=\{v_1,...,v_n\}</math> csúcshalmazú <math>G</math> [[gráf]]hoz egy olyan <math>M(G)</math>-vel jelölt gráfot rendel, melyben [[feszített részgráf]]ként szerepel a <math>G</math> gráf, továbbá még n+1 csúcs. Ezek a következő elrendezésben: Minden <math>G</math>-beli <math>v_i</math> csúcsnak van egy <math>u_i</math> párja, melynek szomszédsága megegyezik a <math>v_i</math> szomszédságával, vagyis azokkal és csak azokkal a csúcsokkal van összekötve, amelyekkel <math>v_i</math>. Az (n+1)-edik új csúcs (<math>w</math>) mindegyik <math>u_i</math> csúccsal össze van kötve, de egyetlen <math>v_i</math>-vel sincs.

 

[[Kép:mycielski.jpg|Mycielski-konstrukció]]

== Irodalmi hivatkozás==

* J. Mycielski: Sur le colorage des graphs, ''Colloquium mathematicum'', '''3'''(1955), 161-162.

 

[[Kategória:Gráfelmélet]]