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 | forrásszöveg szerkesztése]

A Mycielski-konstrukció a V(G)=\{v_1,...,v_n\} csúcshalmazú G gráfhoz egy olyan M(G)-vel jelölt gráfot rendel, melyben feszített részgráfként szerepel a G gráf, továbbá még n+1 csúcs. Ezek a következő elrendezésben: Minden G-beli v_i csúcsnak van egy u_i párja, melynek szomszédsága megegyezik a v_i szomszédságával, vagyis azokkal és csak azokkal a csúcsokkal van összekötve, amelyekkel v_i. Az (n+1)-edik új csúcs (w) mindegyik u_i csúccsal össze van kötve, de egyetlen v_i-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 M_3-mal izomorf, az ábrán jelölt többi csúccsal alkotja az M_4-et.

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

Tétel[szerkesztés | forrásszöveg szerkesztése]

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

Bizonyítás[szerkesztés | forrásszöveg szerkesztése]

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

Teljes indukcióval látjuk be, hogy \chi(G_k)=k. k=2-re az állítás egyértelmű. Tegyük fel, hogy az állítás igaz k-ra. Indirekt belátjuk, hogy ekkor \chi(G_{k+1})=k+1. G_{k+1} színezhető jól k+1 színnel a következő módon: Kiszínezzük a G_k-beli v_i csúcsokat k színnel jól (az indukciós feltevés miatt ez lehetséges), majd minden u_i-t v_i színére és w-t pedig a (k+1)-edik színnel. Azt kell tehát belátni, hogy erre a k+1 színre szükség is van. Mivel G_{k+1} részgráfként tartalmazza a k-kromatikus G_k gráfot, \chi(G_{k+1}) nem lehet kisebb k-nál. Tegyük fel indirekt, hogy \chi(G_{k+1})=k. A színeket 1,2,…,k-val, x csúcs színét c(x)-szel jelöljük. Feltehetjük, hogy c(w)=k. Mivel minden u_i szomszédos w-vel, minden u_i csúcs színe az 1,2,…,k-1 színek valamelyike lehet. Tekintsük a v_i csúcsok által feszített részgráfot, ez G_k-val izomorf. Most megadjuk a v_i csúcsok egy új, c' színezését, mely csak az 1,2,…,k-1 színeket tartalmazza. c(v_i)=k esetén legyen c'(v_i)=c(u_i), minden más esetben c'(v_i)=c(v_i). Azoknál az éleknél, melyek végpontjainak színét nem változtattuk meg, nem lehet probléma. Azon v_i csúcsoknak, melyekre c(v_i)=k teljesül, nincs olyan v_j szomszédja, melyre c(v_j)=k, mert c egy jó színezés volt. Ekkor c'(v_j)=c(v_j) v_i minden v_j szomszédjára teljesül. Gond csak akkor lehet, ha c(u_i)=c'(v_i)=c'(v_j)=c(v_j). c(u_i)=c(v_j) azonban nem teljesül, mert ha v_i és v_j szomszédosak, akkor u_i és v_j is, c pedig jó színezés. Tehát a v_i csúcsok színezhetőek jól úgy, hogy csak az 1,2,…,k-1 színeket használjuk. Ez viszont ellentmond annak, hogy a v_i csúcsok G_k-val izomorf feszített részgráfja k-kromatikus. Emiatt \chi(G_{k+1})>k. Ebből és \chi(G_{k+1})<=k+1-ből az következik, hogy \chi(G_{k+1})=k+1. 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 | forrásszöveg szerkesztése]

A k-kromatikus M_k Mycielski-konstrukcióval kapott gráf csak k=3-ra tartalmaz Euler-kört. M_1 egy pontból, M_2 két pontból és egy élből áll, tehát nem tartalmaznak Euler-kört. M_3 egy 5 pontból álló kör, amiben van Euler-kör. A konstrukcióból adódik, hogy ugyanannyi v típusú csúcs van, mint amennyi u típusú, tehát k\geq 3 esetén w-vel együtt páratlan sok csúcs van. M_{k+1}-ben a w csúcsnak |V(M_k)| szomszédja van, ami k\geq 3 esetén páratlan, így w páratlan fokú. Tehát k>3-ra a Mycielski-gráf nem tartalmaz Euler-kört.

Euler-út a Mycielski-gráfban[szerkesztés | forrásszöveg szerkesztése]

Az M_k Mycielski-gráf csak k=2 és k=3 esetén tartalmaz Euler-utat. Könnyen ellenőrizhető, hogy M_2 és M_3 tartalmaz Euler-utat. A következőkben azt látjuk be, hogy a Mycielski-gráfnak k>3 esetén 2-nél több páratlan fokú csúcsa van, ezért nem tartalmaz Euler-utat. Ha M_k-ban v_i fokszáma d, akkor M_{k+1}-ben u_i fokszáma d+1, hiszen össze van kötve v_i M_k-beli szomszédaival és w-vel, de más csúccsal nem. v_i M_{k+1}-ben össze van kötve az M_k-beli szomszédaival, illetve azok u jelű párjaival, vagyis 2d szomszédja van M_{k+1}-ben. Ebből következik, hogy k\geq 3 esetén, a Mycielski-gráf v-vel jelölt csúcsai páros fokúak, míg az u-val jelölt csúcsai páratlan fokúak, hiszen k\geq 4 esetén minden u csúcs foka 1-gyel nagyobb, mint a párjáé. Ekkor az u_i-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 v_i és u_i párnál a fokszám 1-gyel tér el, tehát v_i és u_i különböző paritású, k>3 esetén pedig 2-nél több ilyen pár van a gráfban.

Hamilton-kör a Mycielski-gráfban[szerkesztés | forrásszöveg szerkesztése]

A Mycielski-gráf k \geq 3 esetén mindig tartalmaz Hamilton-kört. M_1 és M_2 nem tartalmaz Hamilton-kört, M_3 a C_5 5 hosszú körrel izomorf, tehát tartalmaz. Most belátjuk, hogy ha M_k tartalmaz Hamilton-kört, akkor M_{k+1} is. Legyen M_k Hamilton-köre a v_1-v_2-...v_m-v_1 kör. Ekkor M_{k+1}-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. v_1-u_2-v_3-u_4-v_5-u_6-...-u_{m-1}-v_m-u_1-w-u_m-v_{m-1}-u_{m-2}-v_{m-3}-u_{m-4}-...-u_3-v_2-v_1 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 M_k 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 | forrásszöveg szerkesztése]

Gráfok színezése

Irodalmi hivatkozás[szerkesztés | forrásszöveg szerkesztése]

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