Mycielski-konstrukció

A matematika, azon belül a gráfelmélet területén a Mycielski-konstrukció, avagy egy irányítatlan gráfhoz tartozó Mycielski-gráf az eredeti gráfból megadott módon képezett nagyobb gráf.[1] A konstrukció megtartja az eredeti gráf háromszögmentességét, de növeli a kromatikus számot; 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 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 klikkszáma nem változik, míg a kromatikus száma 1-gyel nő.

DefinícióSzerkesztés

 
Az 5-körgráfból Mycielski-konstrukcióval képezett M4 Grötzsch-gráf.

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.

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.

TételSzerkesztés

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

BizonyításSzerkeszté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.

A konstrukció iterációjaSzerkesztés

 
Az M2, M3 és M4 Mycielski-gráfok

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 Mi = M(Mi−1) sorozatát kapjuk, ezeket Mycielski-gráfoknak is nevezzük. A sorozat első néhány eleme az M2 = K2, ami két csúcsból és egy élből áll, az M3 = C5 körgráf és a 11 csúcsból és 20 élből álló Grötzsch-gráf.

Általában véve a sorozat Mi gráfjairól elmondható, hogy háromszögmentesek, (i−1)-szeresen összefüggőek és i-kromatikusak. Az Mi csúcsainak száma 3 · 2i−2 − 1(A083329 sorozat az OEIS-ben). Az Mi éleinek számát (kis i-kre) a következő sorozat adja:

0, 0, 1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, ... (A122695 sorozat az OEIS-ben).

TulajdonságaiSzerkesztés

 
Az M4 (Grötzsch-gráf) Hamilton-köre

Általánosítása: gráf feletti kúpSzerkesztés

A Mycielski-konstrukció egy általánosítása a gráf feletti kúp képzése, amit (Stiebitz 1985) vezetett be, majd (Tardif 2001) és (Lin et al. 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 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 Δ2(G)-nek felel meg.

Euler-kör a Mycielski-gráfbanSzerkeszté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áfbanSzerkeszté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áfbanSzerkeszté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ákSzerkesztés

IrodalomSzerkesztés

JegyzetekSzerkesztés

További információkSzerkesztés