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

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

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.

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.

Tétel

(Mycielski): Minden $k\ge 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 szám felső korlátja nem függ a klikkszámtól.

Bizonyítás

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^{\prime }$ színezését, mely csak az 1,2,…,$k-1$ színeket tartalmazza. $c(v_i)=k$ esetén legyen $c^{\prime }(v_i)=c(u_i)$, minden más esetben $c^{\prime }(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^{\prime }(v_j)=c(v_j)$ $v_i$ minden $v_j$ szomszédjára teljesül. Gond csak akkor lehet, ha $c(u_i)=c^{\prime }(v_i)=c^{\prime }(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.

A konstrukció iterációja

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

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

0, 0, 1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, ... Sablon:OEIS.

Tulajdonságai

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

• Ha G n csúccsal és m éllel rendelkezik, akkor M(G) 2n+1 csúccsal és 3m+n éllel fog rendelkezni.
• Ha G kromatikus száma k, akkor M(G) kromatikus száma k + 1 Sablon:Harv.
• Ha G háromszögmentes, akkor M(G) is az Sablon:Harv.
• Általánosabban, ha G klikkszáma ω(G), akkor M(G) klikkszáma max(2,ω(G)). Sablon:Harv.
• Ha G faktorkritikus gráf, akkor M(G) is az Sablon:Harv. Elmondható továbbá, hogy az M_i gráfok mindegyike, i ≥ 2-től faktorkritikus.
• Ha G-nek van Hamilton-köre, akkor M(G)-nek is van. Sablon:Harv
• Ha G dominálási száma γ(G), akkor M(G) dominálási száma γ(G)+1. Sablon:Harv

Általánosítása: gráf feletti kúp

A Mycielski-konstrukció egy általánosítása a gráf feletti kúp képzése, amit Sablon:Harvtxt vezetett be, majd Sablon:Harvtxt és Sablon:Harvtxt 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 Δ₂(G)-nek felel meg.

Euler-kör a Mycielski-gráfban

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\ge 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\ge 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

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\ge 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\ge 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

A Mycielski-gráf $k\ge 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

• Gráfok színezése

Irodalom

• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation. As cited by Sablon:Harvtxt.
• Sablon:Citation.

További információk

• Sablon:Mathworld