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.