„Mycielski-konstrukció” változatai közötti eltérés

[nem ellenőrzött változat][nem ellenőrzött változat]
Tartalom törölve Tartalom hozzáadva
Vhalasz (vitalap | szerkesztései)
Új oldal, tartalma: „==Mycielski-konstrukció== A Mycielski-konstrukció <math>V(G)=\{v_1,...,v_n\}</math> csúcshalmaz <math>G</math> gráfhoz egy olyan <math>M(G)</math>-vel jelölt gráfot ...”
 
Vhalasz (vitalap | szerkesztései)
2. sor:
A Mycielski-konstrukció <math>V(G)=\{v_1,...,v_n\}</math> csúcshalmaz <math>G</math> gráfhoz egy olyan <math>M(G)</math>-vel jelölt gráfot rendel, melyben feszített részgráfként szerepel a <math>G</math> gráf, továbbá még n+1 csúcs. Ezek a következő elrendezésben: Minden <math>G</math>-beli <math>v_i</math> csúcsnak van egy <math>u_i</math> párja, melynek szomszédsága megegyezik a <math>v_i</math> szomszédságával, vagyis azokkal és csak azokkal a csúcsokkal van összekötve, amelyekkel <math>v_i</math>. Az (n+1)-edik új csúcs (<math>w</math>) mindegyik <math>u_i</math> csúccsal össze van kötve, de egyetlen <math>v_i</math>-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.
 
[[Kép:mycielski.jpg|Mycielski-konstrukció]]
 
Az ábrán az alsó öt csúcs által feszített részgráf az <math>M_3</math>-mal izomorf, az ábrán jelölt többi csúccsal alkotja az <math>M_4</math>-et.
 
Megjegyzés: Az <math>M_4</math>-et [[Grötzsch-gráf]]nak is szokás nevezni.
 
 
 
'''Tétel''': Minden k>=2 egész számra létezik olyan <math>G_k</math> gráf, melyre <math>\omega(G_k)=2</math> és <math>\chi(G_k)=k</math>. Ez azt jelenti, hogy a kromatikus szám felső korlátja nem függ a klikkszámtól.
11 ⟶ 19 sor:
Teljes indukcióval látjuk be, hogy <math>\chi(G_k)=k</math>. 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 <math>\chi(G_{k+1})=k+1</math>. <math>G_{k+1}</math> színezhető jól k+1 színnel a következő módon: Kiszínezzük a <math>G_k</math>-beli <math>v_i</math> csúcsokat k színnel jól (az indukciós feltevés miatt ez lehetséges), majd minden <math>u_i</math>-t <math>v_i</math> színére és <math>w</math>-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 <math>G_{k+1}</math> részgráfként tartalmazza a k-kromatikus <math>G_k</math> gráfot, <math>\chi(G_{k+1})</math> nem lehet kisebb k-nál. Tegyük fel indirekt, hogy <math>\chi(G_{k+1})=k</math>.
A színeket 1,2,...,k-val, <math>x</math> csúcs színét <math>c(x)</math>-szel jelöljük. Feltehetjük, hogy <math>c(w)=k</math>. Mivel minden <math>u_i</math> szomszédos <math>w</math>-vel, minden <math>u_i</math> csúcs színe az 1,2,...,k-1 színek valamelyike lehet. Tekintsük a <math>v_i</math> csúcsok által feszített részgráfot, ez <math>G_k</math>-val izomorf. Most megadjuk a <math>v_i</math> csúcsok egy új, <math>c'</math> színezését, mely csak az 1,2,...,k-1 színeket tartalmazza. <math>c(v_i)=k</math> esetén legyen <math>c'(v_i)=c(u_i)</math>, minden más esetben <math>c'(v_i)=c(v_i)</math>. Azoknál az éleknél, melyek végpontjainak színét nem változtattuk meg, nem lehet probléma. Azon <math>v_i</math> csúcsoknak, melyekre <math>c(v_i)=k</math> teljesül, nincs olyan <math>v_j</math> szomszédja, melyre <math>c(v_j)=k</math>, mert <math>c</math> egy jó színezés volt. Ekkor <math>c'(v_j)=c(v_j)</math> <math>v_i</math> minden <math>v_j</math> szomszédjára teljesül. Gond csak akkor lehet, ha <math>c(u_i)=c'(v_i)=c'(v_j)=c(v_j)</math>. <math>c(u_i)=c(v_j)</math> azonban nem teljesül, mert ha <math>v_i</math> és <math>v_j</math> szomszédosak, akkor <math>u_i</math> és <math>v_j</math> is, <math>c</math> pedig jó színezés. Tehát a <math>v_i</math> 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 <math>v_i</math> csúcsok <math>G_k</math>-val izomorf feszített részgráfja k-kromatikus. Emiatt <math>\chi(G_{k+1})>k</math>. Ebből és <math>\chi(G_{k+1})<=k+1</math>-ből az következik, hogy <math>\chi(G_{k+1})=k+1</math>.
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==