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