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

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.

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

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.

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

• 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)

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.

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.

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.

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.

• Gráfok színezése

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

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