Klikkek mérete és a kromatikus szám kapcsolata

Definíció: Egy K csúcshalmaz klikk, ha K bármely két különbözõ eleme összekötött.

Megjegyzés: tetszõleges egy elemû ponthalmaz klikk. Tetszõleges nem hurokél él két végpontja két elemû klikket alkot.

A klikkek esetén az érdekes minél nagyobb klikket felmutatni.

Definíció: omega(G)=max{|K|:K klikk G-ben}.

A klikkparaméter és kromatikus szám nyilvánvaló kapcsolatban áll egymással. Egy klikk ``kényszeríti '' a színezõt, hogy a klikk minden csúcsánál különbözõ színt használjon fel. Azaz omega(G)<₌khi(G).

Van-e fordított irányú kapcsolat? Nagy kromatikus szám esetén mondhatunk-e valamit a klikkparaméter nagyságáról? A válasz: NEM. Van olyan gráfsorozat, amely elemeinek kromatikus száma tetszõlegesen nagy lehet, míg egyik gráf sem tartalmaz három elemû klikket (gráfelméleti szlenggel háromszöget) Azaz klikkparamétere a lehetõ legkisebb nem hurokél él megléte mellett. Ilyen gráfsorozatra adunk példákat.

1. konstrukció: Rekurzív módon/indukció segítségével írunk le egy G_n gráfsorozatot.

G₂ legyen egy két pontú teljes gráf, amely kromatikus száma 2, míg nem tartalmaz három elemû klikket (mivel nincs is három csúcsa).

Tegyük fel, hogy már definiáltuk G_n-1-et és ennek kromatikus száma n-1, de nem tartalmaz három elemû klikket. Ennek segítségevel írunk le G_n gráfot, amely kromatikus száma eggyel nagyobb lesz (n), de továbbra sem tartalmaz háromszöget. Vegyünk egy (|V(G_n-1)|-1)(n-1)+1 elemû U ponthalmazt, amely pontok között nem vezet él. Így a színezésnél ezek színezésere nincs feltétel (tetszõleges lehet). A trükkös elemszám választás lényege, hogy bárhogyan is színezzük a csúcsokat n-1 színnel lesz egy legalább |V(G_n-1)| elemû részhalmaz, amely elemei ugyanazt a színt kapják. U összes |V(G_n-1)| elemû részhalmazához vegyük fel G_n-1 egy-egy példányát és mindegyik részhalmaz elemit párosítsuk élekkel a hozzátartozó G_n-1 példány csúcsaival. Az így nyert gráf lesz G_n.

G_n kromatikus száma valóban nõtt G_n-1-éhez képest. Ha G_n-et n-1 színnel színezzük, akkor tudjuk, hogy az U ponthalmaz valamely |V(G_n)| elemû R részhalmazának elemi ugyanazt a színt kapják, de ehhez tartozik G_n-1 egy példánya, amelynek minden eleme R egy elemével párosított, így speciálisan nem kaphatja R elemeinek közös színét. Tehát a megfelelõ G_n-1 színezésére az n-1 színû palettáról már csak n-2 szín maradt, ami nem elég. Az, hogy a kromatikus szám növekedése csak 1, az könnyen ellenõrizhetõ.

Ha G_n-1 nem tartalmazott háromszöget, akkor G_n sem tartalmaz. Ez szintén egyszerûen látható

2. konstrukció: (Mycielsky) Ismét rekurzív módon/indukció segítségével írunk le egy G_n gráfsorozatot.

G₂ legyen egy két pontú teljes gráf, amely kromatikus száma 2, míg nem tartalmaz három elemû klikket (mivel nincs is három csúcsa).

Tegyük fel, hogy már definiáltuk G_n-1-et és ennek kromatikus száma n-1, de nem tartalmaz három elemû klikket. Ennek segítségével írunk le G_n gráfot, amely kromatikus száma eggyel nagyobb lesz (n), de továbbra sem tartalmaz háromszöget.

Vegyük G_n-1 egy példányát és minden v csúcs mellé vegyünk fel egy v' ``ikertestvért''. A v' csúcsokra mint új csúcsokra hivatkozunk. Az új csúcsok között ne vezessen él, de minden v' csúcsot kössünk össze a v csúcs szomszédaival. Végül adjunk hozzá az így kapott gráfhoz egy z zárócsúcsot, amelyet pontosan a v' új csúcsokkal kötünk össze. Az így kapott gráf lesz G_n.

A G_n-re történõ ugrás során nem keletkezhet háromszög.

A G_n-re történõ ugrás során pontosan eggyel nõ a kromatikus szám. Nyilván eggyel többel nem nõhet. A növekedés abból ered, hogy tegyük fel, hogy G_n-t jól kiszínezzük n-1 színnel. z színe legyen n-1, az utolsó szín. Belátjuk, hogy a G_n színezése közben kiszínezett G_n-1 jól átszínezhetõ úgy, hogy a benne elõforduló n-1 színek eltünjenek. Ez ellentmond, annak, hogy G_n-1 kromatikus száma n-1. Az átszínezés egyeszerû. Minden 1,2,...,n-2 színt meghagyunk. Az n-1 színt kapottv csúcsok színét lecseréljük v' ikertestvére színére. Ez a szín nem lehet n-1, hiszen v' összekötött z-vel. Másrészt jó színezéshez jutunk, hisz egy független ponthalmaz (az n-1 színû pontok egy halmaza) elemeit festettük át, köztük a jó színezés semmilyen feltételt nem ír elõ. Míg az átszínezett pontoknak a régi színekkel sem lesz konfliktusa, hisz v mellé a v' színe stimmelni fog, hiszen v' színe egy jó színezésbõl jött, ahol v' összekötött v G_n-1-beli szomszédaival.

3. konstrukció: Vegyünk fel egy egyenest és rajta n pontot. Az n pont által meghatározott (ⁿ₂) darab szakaszra mint átmérõre köröket rajzolunk. Az így kapott (ⁿ₂) darab kör alkotja G_n gráf csúcshalmazát. Két kör szomszédos, ha kívülrõl érintkeznek.

Egyszerûen igazolható, hogy ezen gráfban nincs háromszög. Azaz az állítás geometriai megfogalmazása: ha három kör középpontja egy egyeensre esik, akkor nem lehetnek páronként kívülrõl érintkezõk.

Ha n > 2^k, akkor G_n nem színezhetõ k színnel. Valóban legyen c köreink egy k színnel történõ színezése (nem feltétlenül jó színezés, igazából célunk az, hogy belássuk ez a színezés nem lehet jó). Az egyenesen felvett kiinduló ponthalmazunk mindegyik P eleméhez rendeljük hozzá azon színek halmazát, amelyeket azon körök kaptak, amelyek egyenesre esõ átmérõjére P mint bal oldali végpont illeszzkedik. Az n (> 2) mindegyikéhez a k elemû paletta egy részhalmazát rendeltük, ami 2^k lehetõséget enged meg a színhalmazokra. n választása miatt lesz két pont P és Q, amelyhez ugyanaz a szín tartozik. Tegyük fel, hogy egyenesünkön balról jobbra haladva elõször P, majd Q következik. Azaz a PQ szakasz bal oldali végpontja P. Azaz a P-hez rendelt színhalmaz elemei között ott van a PQ-ra mint átmérõre rajzolt C kör színe. Ennek a színnek elõ kell fordulnia a Q-hoz rendelt színhalmazban is. Ez egy megfelelõ kör létezését kívanja, ami azonos színû C-vel, amit kívülrõl érint. Tehát a kiinduló c színezés nem lehet jó színezés G_n kromatikus száma legalább k+1.

A fenti konstrukció egy absztraktabb megfogalmazása a következõ: Legyen K_n az n pontú teljes gráf. Csuácsit számozzuk meg 1-tõl n-ig, amjd minden élt irányítsunk a kisebb számtól a nagyobb felé. A teljes gráf irányításával kapott gráfokat turnamenteknek nevezzük. A fenti irányítás speciális, tranzitív turnamentnek nevezik.

Az így kapott T_n irányított gráfnak lehet az élgráfját venni. Az L(T_n) élgráf csúcsai T élei lesznek. Két L(T_n) csúcs (T_n él) összekötött, ha mint T_n-beli élek irányításukat figyelembe véve is csatlakoznak. L(T_n) is irányított gráf lesz, habár színezési szempontból az irányítás elfelejthetõ. G_n a most leírt L(T_n) lesz (irányítás elfelejtésével). Ez valóban ugyanaz, mint a geometria nyelvezettel leírt konstrukció. K_n csúcsai felelnek meg az egyenesen felvett pontoknak. A K_n csúcsainak számozása az egyenesen lévõ balról jobbra sorrendnek felel meg. Az élek vizsgálata a szakaszok, illetve a ráírt körök vételével egyenértékû. Ezek az élek/körök alkotják a csúcshalmazt. Az összekötöttség G_n-ben pedig a csatlakozás K_n élei közt, ami a kívülrõl érintkezés a körök nyelvezetén.

4. konstrukció: A 3. konstrukció az utolsó nyelvezetben történõ megfogalmazása könnyen általánosítható:

Legyen I egy irányított gráf, amely nem tartalmaz irányított háromszöget és kromatikus száma K (a színezésnél az irányítás elveszti jelentõségét). Ekkor ennek L(I) élgráfját véve olyan gráfot kapunk (az irányítást elhagyjuk), amely

1. nem tartalmaz háromszöget,
2. k kromatikus számára K <₌ 2^k.

1. ellenõrzése egyszerû. 2-höz vegyünk L(I) egy tetszõleges jó színezését. Ekkor L(I) csúcsait, azaz I éleit színezzük. I minden csúcsára vizsgáljuk meg a belõle kiinduló élek halmazában (L(I)-ben csúcsok halmaza) kiosztott színek halmazát. Ezek a színhalmazok a k szín 2^k-féle részhalmazából kerülnek ki. Belátjuk, hogy két I-ben összekötött csúcshoz rendelt színhalmaz különbözõ, azaz a csúcsokhoz rendelt színhalamzok felfoghatók I egy jó színezéséhez. Azaz I kromatikus száma (K) nem haladhatja meg a felhasznált színek számát (legfeljebb 2^k), ami éppen a bizonyítandó. Tegyük fel, hogy I-ben x-bõl vezet egy e él y-hoz. Ekkor e színe (nevezzük ezt pirosnak) ott van az x-hez rendelt színhalmazban. L(I)-t jól színeztük. Így az y-ból kivezetõ élek között nem lehet már piros. Az y-hoz rendelt színhalmazban nincs ott a piros szín. Azaz x és y színhalmaza különbözik.

• minden p csúcsra B(p,1) egy csillag,
• minden p csúcsra B(p,k) egy páros gráf,
• minden p csúcsra B(p,k) csak a szélességi keresés éleit tartalmazza.

• nincs háromszög a gráfban,
• minden páratlan hosszú kör hossza nagyobb mint 2k+1,
• minden kör hossza nagyobb mint 2k+1.