Mycielski-konstrukció

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

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é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.

A konstrukció iterációja[szerkeszté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ágai[szerkesztés]

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

Általánosítása: gráf feletti kúp[szerkeszté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á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]

Irodalom[szerkesztés]

Chvátal, Vašek (1974), "The minimality of the Mycielski graph", Graphs and Combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973), vol. 406, Lecture Notes in Mathematics, Springer-Verlag, pp. 243–246.

Došlić, Tomislav (2005), "Mycielskians and matchings", Discussiones Mathematicae Graph Theory 25 (3).

Fisher, David C.; McKenna, Patricia A. & Boyer, Elizabeth D. (1998), "Hamiltonicity, diameter, domination, packing, and biclique partitions of Mycielski's graphs", Discrete Applied Mathematics 84 (1–3): 93–105, DOI 10.1016/S0166-218X(97)00126-1.

Lin, Wensong; Wu, Jianzhuan & Lam, Peter Che Bor et al. (2006), "Several parameters of generalized Mycielskians", Discrete Applied Mathematics 154 (8): 1173–1182, DOI 10.1016/j.dam.2005.11.001.

Mycielski, Jan (1955), "Sur le coloriage des graphes", Colloq. Math. 3: 161–162, <http://matwbn.icm.edu.pl/ksiazki/cm/cm3/cm3119.pdf>.

Stiebitz, M. (1985), Beiträge zur Theorie der färbungskritschen Graphen, Habilitation thesis, Technische Universität Ilmenau. As cited by (Tardif 2001).

Tardif, C. (2001), "Fractional chromatic numbers of cones over graphs", Journal of Graph Theory 38 (2): 87–94, DOI 10.1002/jgt.1025.

További információk[szerkesztés]