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 kormatikus 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 kormatikus 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, amley 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, amleynek 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 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 kormatikus 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ü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ócsucsot, 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, koztü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 > 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.
Ekkor ennek L(I) élgráfját véve
olyan gráfot kapunk, amely nem tartalmaz semilyen háromszöget.
Legyen ...