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\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 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'$ 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.

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 $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

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

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

• Gráfok színezése

Irodalom

• 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

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