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ó

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

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

Tétel

(Mycielski): Minden ${\displaystyle k\geq 2}$ egész számra létezik olyan ${\displaystyle G_{k}}$ gráf, melyre ${\displaystyle \omega (G_{k})=2}$ és ${\displaystyle \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 ${\displaystyle G_{k}}$ egyetlen ${\displaystyle k}$-ra sem tartalmaz háromszöget, azaz a klikkszáma 2. ${\displaystyle k=2}$-re igaz az állítás, hiszen ${\displaystyle G_{2}}$ a 2 pontú teljes gráf. Tegyük fel, hogy ${\displaystyle G_{k}}$-ban nincs háromszög. Indirekt bizonyítással belátjuk, hogy ${\displaystyle G_{k+1}}$-ben sincs. Tegyük fel, hogy mégis van ${\displaystyle G_{k+1}}$-ben háromszög. Ennek a háromszögnek legalább az egyik csúcsa nincs ${\displaystyle G_{k}}$-ban, mert ${\displaystyle G_{k}}$ az indukciós feltevés szerint nem tartalmaz háromszöget. Ha a háromszög tartalmazza a ${\displaystyle w}$-vel jelölt csúcsot, akkor a másik két csúcs csak ${\displaystyle u}$-val jelölt lehet, azok azonban nincsenek összekötve. Már csak az az eset maradt, hogy a háromszög tartalmaz egy ${\displaystyle u}$-val jelölt csúcsot (${\displaystyle u_{i}}$). Ekkor a másik két csúcs csak ${\displaystyle v_{x}}$ és ${\displaystyle v_{y}}$ lehet. ${\displaystyle u_{i}}$ pontosan azokkal a csúcsokkal van összekötve, amelyekkel ${\displaystyle v_{i}}$, vagyis ${\displaystyle v_{i}}$, ${\displaystyle v_{x}}$ és ${\displaystyle v_{y}}$ is háromszöget alkot ${\displaystyle G_{k}}$-ban, ez pedig ellentmond az indukciós feltevésnek.

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

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 (Mycielski 1955).
• Ha G háromszögmentes, akkor M(G) is az (Mycielski 1955).
• Általánosabban, ha G klikkszáma ω(G), akkor M(G) klikkszáma max(2,ω(G)). (Mycielski 1955).
• Ha G faktorkritikus gráf, akkor M(G) is az (Došlić 2005). 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. (Fisher, McKenna & Boyer 1998)
• Ha G dominálási száma γ(G), akkor M(G) dominálási száma γ(G)+1. (Fisher, McKenna & Boyer 1998)

Á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 (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 Δ₂(G)-nek felel meg.

Euler-kör a Mycielski-gráfban

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

Euler-út a Mycielski-gráfban

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

• .
• .
• .
• .
• .
• . As cited by (Tardif 2001).
• .

Jegyzetek

1. Jan Mycielski (1955)

További információk

• Weisstein, Eric W.: Mycielski Graph (angol nyelven). Wolfram MathWorld