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 Gn gráfsorozatot.

G2 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 Gn-1-et és ennek kromatikus száma n-1, de nem tartalmaz három elemű klikket. Ennek segítségevel írunk le Gn gráfot, amely kromatikus száma eggyel nagyobb lesz (n), de továbbra sem tartalmaz háromszöget. Vegyünk egy (|V(Gn-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(Gn-1)| elemű részhalmaz, amely elemei ugyanazt a színt kapják. U összes |V(Gn-1)| elemű részhalmazához vegyük fel Gn-1 egy-egy példányát és mindegyik részhalmaz elemit párosítsuk élekkel a hozzátartozó Gn-1 példány csúcsaival. Az így nyert gráf lesz Gn.

Gn kromatikus száma valóban nőtt Gn-1-éhez képest. Ha Gn-et n-1 színnel színezzük, akkor tudjuk, hogy az U ponthalmaz valamely |V(Gn)| elemű R részhalmazának elemi ugyanazt a színt kapják, de ehhez tartozik Gn-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ő Gn-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 Gn-1 nem tartalmazott háromszöget, akkor Gn 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 Gn gráfsorozatot.

G2 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 Gn-1-et és ennek kromatikus száma n-1, de nem tartalmaz három elemű klikket. Ennek segítségével írunk le Gn gráfot, amely kromatikus száma eggyel nagyobb lesz (n), de továbbra sem tartalmaz háromszöget.

Vegyük Gn-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 Gn.

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

A Gn-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 Gn-t jól kiszínezzük n-1 színnel. z színe legyen n-1, az utolsó szín. Belátjuk, hogy a Gn színezése közben kiszínezett Gn-1 jól átszínezhető úgy, hogy a benne előforduló n-1 színek eltünjenek. Ez ellentmond, annak, hogy Gn-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 Gn-1-beli szomszédaival.


3. konstrukció: Vegyünk fel egy egyenest és rajta n pontot. Az n pont által meghatározott (n2) darab szakaszra mint átmérőre köröket rajzolunk. Az így kapott (n2) darab kör alkotja Gn 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 > 2k, akkor Gn 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 2k 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 Gn kromatikus száma legalább k+1.


A fenti konstrukció egy absztraktabb megfogalmazása a következő: Legyen Kn 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 Tn irányított gráfnak lehet az élgráfját venni. Az L(Tn) élgráf csúcsai T élei lesznek. Két L(Tn) csúcs (Tn él) összekötött, ha mint Tn-beli élek irányításukat figyelembe véve is csatlakoznak. L(Tn) is irányított gráf lesz, habár színezési szempontból az irányítás elfelejthető. Gn a most leírt L(Tn) lesz (irányítás elfelejtésével). Ez valóban ugyanaz, mint a geometria nyelvezettel leírt konstrukció. Kn csúcsai felelnek meg az egyenesen felvett pontoknak. A Kn 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 Gn-ben pedig a csatlakozás Kn é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 <= 2k.

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 2k-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 2k), 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.


A fent leírt gráf sorozatok elemit úgy foghatjuk fel, hogy a színezés szempontjából globálisan nehezek (nagy a kromatikus számuk). Lokálisan azonban egyszerűek. Ha egy tetszőleges csúcsában állunk és csak helyünk szomszédait látjuk, akkor ey független ponthalmazt látunk (őket nem köti él), azon túl, hogy lokális pozíciónk színétől eltérő színt kell adnunk (a triviális előirás) nincs más feltétel. Azaz a színezésnek nincs lokális nehézsége. Ezt a lokális könnyűséget nehezíthetjük is. Egy szélességi keresséssel lokális p pozíciónk k sugarú környezetét meghatározhatjuk. Feltesszük, hogy ezt a k sugarú B(p,k) környezetet (a csúcsokat és a köztük menő éleket) látjuk a p-ben állva. Nézzük a következő feltételeket: Ezek a feltételek ekvivalensek a következőkkel: Nyilván k>1 esetén a három feltétel egyre megszorítóbb lesz. k növelésével a feltétel kielégítése egyre nehezebb lesz. Ennek ellenére minden fix k természetes számra megadható olyan gráf, amely a feltételt kielégíti, de kromatikus száma tetszőlegesen nagy lehet.