Mycielski-konstrukció

A Wikipédiából, a szabad enciklopédiából

Ismert, hogy a klikkszám egy alsó korlátja a kromatikus számnak. 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 a klikkszáma nem változik, míg a kromatikus száma 1-gyel nő.

Definíció[szerkesztés]

A Mycielski-konstrukció a csúcshalmazú gráfhoz egy olyan -vel jelölt gráfot rendel, melyben feszített részgráfként szerepel a gráf, továbbá még n+1 csúcs. Ezek a következő elrendezésben: Minden -beli csúcsnak van egy párja, melynek szomszédsága megegyezik a szomszédságával, vagyis azokkal és csak azokkal a csúcsokkal van összekötve, amelyekkel . Az (n+1)-edik új csúcs () mindegyik csúccsal össze van kötve, de egyetlen -vel sincs. Mycielski-gráfoknak azokat a gráfokat nevezzük, amelyek a két csúcsú teljes gráfbó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.

Groetzsch-as-Mycielski.png

Az ábrán a felső öt csúcs által feszített részgráf az -mal izomorf, az ábrán jelölt többi csúccsal alkotja az -et.

Megjegyzés: Az -et Grötzsch-gráfnak is szokás nevezni.

Tétel[szerkesztés]

(Mycielski): Minden egész számra létezik olyan gráf, melyre és . Ez azt jelenti, hogy a kromatikus felső korlátja nem függ a klikkszámtól.

Bizonyítás[szerkesztés]

Teljes indukcióval belátjuk, hogy egyetlen -ra sem tartalmaz háromszöget, azaz a klikkszáma 2. -re igaz az állítás, hiszen a 2 pontú teljes gráf. Tegyük fel, hogy -ban nincs háromszög. Indirekt bizonyítással belátjuk, hogy -ben sincs. Tegyük fel, hogy mégis van -ben háromszög. Ennek a háromszögnek legalább az egyik csúcsa nincs -ban, mert az indukciós feltevés szerint nem tartalmaz háromszöget. Ha a háromszög tartalmazza a -vel jelölt csúcsot, akkor a másik két csúcs csak -val jelölt lehet, azok azonban nincsenek összekötve. Már csak az az eset maradt, hogy a háromszög tartalmaz egy -val jelölt csúcsot (). Ekkor a másik két csúcs csak és lehet. pontosan azokkal a csúcsokkal van összekötve, amelyekkel , vagyis , és is háromszöget alkot -ban, ez pedig ellentmond az indukciós feltevésnek.

Teljes indukcióval látjuk be, hogy . -re az állítás egyértelmű. Tegyük fel, hogy az állítás igaz -ra. Indirekt belátjuk, hogy ekkor . színezhető jól színnel a következő módon: Kiszínezzük a -beli csúcsokat színnel jól (az indukciós feltevés miatt ez lehetséges), majd minden -t színére és -t pedig a -edik színnel. Azt kell tehát belátni, hogy erre a színre szükség is van. Mivel részgráfként tartalmazza a -kromatikus gráfot, nem lehet kisebb -nál. Tegyük fel indirekt, hogy . A színeket 1,2,…,-val, csúcs színét -szel jelöljük. Feltehetjük, hogy . Mivel minden szomszédos -vel, minden csúcs színe az 1,2,…, színek valamelyike lehet. Tekintsük a csúcsok által feszített részgráfot, ez -val izomorf. Most megadjuk a csúcsok egy új, színezését, mely csak az 1,2,…, színeket tartalmazza. esetén legyen , minden más esetben . Azoknál az éleknél, melyek végpontjainak színét nem változtattuk meg, nem lehet probléma. Azon csúcsoknak, melyekre teljesül, nincs olyan szomszédja, melyre , mert egy jó színezés volt. Ekkor minden szomszédjára teljesül. Gond csak akkor lehet, ha . azonban nem teljesül, mert ha és szomszédosak, akkor és is, pedig jó színezés. Tehát a csúcsok színezhetőek jól úgy, hogy csak az 1,2,…, színeket használjuk. Ez viszont ellentmond annak, hogy a csúcsok -val izomorf feszített részgráfja k-kromatikus. Emiatt . Ebből és -ből az következik, hogy . A fenti tételnek a következménye, hogy a kromatikus számra nem adható felső becslés a klikkszám segítségével.

Euler-kör a Mycielski-gráfban[szerkesztés]

A -kromatikus Mycielski-konstrukcióval kapott gráf csak -ra tartalmaz Euler-kört. egy pontból, két pontból és egy élből áll, tehát nem tartalmaznak Euler-kört. egy 5 pontból álló kör, amiben van Euler-kör. A konstrukcióból adódik, hogy ugyanannyi típusú csúcs van, mint amennyi típusú, tehát esetén -vel együtt páratlan sok csúcs van. -ben a csúcsnak szomszédja van, ami esetén páratlan, így páratlan fokú. Tehát -ra a Mycielski-gráf nem tartalmaz Euler-kört.

Euler-út a Mycielski-gráfban[szerkesztés]

Az Mycielski-gráf csak és esetén tartalmaz Euler-utat. Könnyen ellenőrizhető, hogy és tartalmaz Euler-utat. A következőkben azt látjuk be, hogy a Mycielski-gráfnak esetén 2-nél több páratlan fokú csúcsa van, ezért nem tartalmaz Euler-utat. Ha -ban fokszáma , akkor -ben fokszáma , hiszen össze van kötve -beli szomszédaival és -vel, de más csúccsal nem. -ben össze van kötve az -beli szomszédaival, illetve azok jelű párjaival, vagyis szomszédja van -ben. Ebből következik, hogy esetén, a Mycielski-gráf -vel jelölt csúcsai páros fokúak, míg az -val jelölt csúcsai páratlan fokúak, hiszen esetén minden csúcs foka 1-gyel nagyobb, mint a párjáé. Ekkor az -k száma mindig nagyobb kettőnél.

Megjegyzés: A probléma úgy is megközelíthető, hogy a konstrukcióból adódóan minden és párnál a fokszám 1-gyel tér el, tehát és különböző paritású, esetén pedig 2-nél több ilyen pár van a gráfban.

Hamilton-kör a Mycielski-gráfban[szerkesztés]

A Mycielski-gráf esetén mindig tartalmaz Hamilton-kört. és nem tartalmaz Hamilton-kört, a 5 hosszú körrel izomorf, tehát tartalmaz. Most belátjuk, hogy ha tartalmaz Hamilton-kört, akkor is. Legyen Hamilton-köre a kör. Ekkor -ben létezik a következő kör, mert a felsorolásban szomszédos csúcsok között a konstrukcióból adódóan mindenhol van él. Ennek a felsorolásnak az első és utolsó csúcsa megegyezik, továbbá minden csúcsot pontosan egyszer tartalmaz, tehát Hamilton-kör. A felsorolás helyességéhez az is kell, hogy páratlan számú csúcsot tartalmazzon, ez a konstrukcióból adódóan teljesül is.

Kapcsolódó témák[szerkesztés]

Irodalmi hivatkozás[szerkesztés]

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