„Mycielski-konstrukció” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
Syp (vitalap | szerkesztései) a Gráfműveletek kategória hozzáadva (a HotCattel) |
Syp (vitalap | szerkesztései) Nincs szerkesztési összefoglaló |
||
1. sor:
A [[matematika]], azon belül a [[gráfelmélet]] területén a '''Mycielski-konstrukció''', avagy egy [[irányítatlan gráf]]hoz tartozó '''Mycielski-gráf''' az eredeti gráfból megadott módon képezett nagyobb gráf{{harvs|first=Jan|last=Mycielski|authorlink=Jan Mycielski|year=1955|txt}}. A konstrukció megtartja az eredeti gráf [[háromszögmentes gráf|háromszögmentességét]], de növeli a [[kromatikus szám]]ot; a konstrukciót ismételten alkalmazva Mycielski igazolta a [[tetszőlegesen nagy]] kromatikus számú háromszögmentes gráfok létezését.
Ismert, hogy a [[gráfelméleti fogalomtár#Klikkek|klikkszám]] egy alsó korlátja a [[kromatikus szám]]nak. Ezért felvetődik az a kérdés, hogy adható-e a klikkszám segítségével felső korlát a kromatikus számra. Ennek a kérdésnek a megválaszolásához Mycielski egy olyan konstrukciót használt, amely egy gráfot úgy egészít ki, hogy
==Definíció==
[[Image:Grötzsch graph as a Mycielskian.svg|thumb|360px|Az 5-[[körgráf]]ból Mycielski-konstrukcióval képezett M<sub>4</sub> [[Grötzsch-gráf]].]]
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.
Mycielski-gráfoknak azokat a gráfokat nevezzük, amelyek a két csúcsú [[teljes gráf]]ból, vagyis a két pontból és egyetlen élből álló gráfból előállíthatóak a fenti eljárás egymás után következő véges számú alkalmazásával.
Az ábrán a felső öt csúcs által feszített részgráf az <math>M_3</math>-mal izomorf, az ábrán jelölt többi csúccsal alkotja az <math>M_4</math>-et.
==Tétel==
45 ⟶ 43 sor:
* J. Mycielski: Sur le colorage des graphs, ''Colloquium mathematicum'', '''3'''(1955), 161-162.
[[Kategória:Gráfműveletek]]
| |||