Kromatikus szám, klikk, perfekt gráfok

A legkevesebb színt, amivel egy gráf csúcsait kiszinezhetjük úgy, hogy a szomszédos csúcsok ne legyenek egyforma színűek, a gráf kromatikus számának nevezzük.

Jele: $\chi (G)$.

Egy $G$ egyszerű gráfban klikknek nevezzük azokat a részgráfokat, amelyek teljes gráfok.

Egy gráf klikkszáma a gráfban található maximális klikk elemszáma.

A $G$ gráf klikkszámát $\omega (G)$-vel jelöljük.

Minden gráfban a klikkszám alsó becslés a kromatikus számra:

\( \omega (G) \leq \chi (G) \)

A $G$ gráfban a $G'$ részgráf feszített részgráf, ha bármely két csúcs a $G'$ gráfban pontosan akkor szomszédos, ha $G$-ben is szomszédos.

Ha egy $G$ gráf minden $G'$ feszített részgráfjára igaz, hogy

\( \omega (G') = \chi (G') \)

akkor a $G$ gráfot perfekt gráfnak nevezzük.

Ha egy gráf perfekt, akkor a kromatikus száma egyenlő a klikkszámával. Az állítás fordítva nem igaz, abból, hogy $\omega (G') = \chi (G')$ még nem következik, hogy a gráf perfekt.

\( \omega(G) \leq \chi(G) \leq \Delta(G) + 1 \)

ahol $\omega(G)$ a gráf klikkszáma, $\chi(G)$ a kromatikus száma és $\Delta(G)$ a maximális fokszáma.

A mohó színezés egy algoritmus a gráfok színezésére.

Lényege, hogy sorba rakjuk a gráf csúcsait, és elkezdjük színezni úgy, hogy minden csúcs színezéséhez a lehető legkisebb sorszámú színt használjuk. Ezt addig folytatjuk, amíg az összes csúcs ki nem lesz színezve, és így elhasználunk legfeljebb $\Delta(G)+1$ darab színt.

Ha $G$ nem teljes gráf, vagy páratlan csúcsú kör, akkor

\( \chi(G) \leq \Delta(G) \)

Egy $G$ gráfban azt a legkisebb számot, amire a gráfnak már van jó élszínezése, a $G$ gráf élkromatikus számának nevezzük.

Jele: $\chi_e$

A Vizing-tétel a gráfok élkromatikus számára ad alsó és felső becslést:

\( \Delta(G) \leq \chi_e(G) \leq \Delta(G) + 1 \)

Vagyis a $G$ egyszerű gráfok két osztályba sorolhatók:

Első osztály: $\chi_e(G) = \Delta(G)$

Második osztály: $\chi_e(G) = \Delta(G)+1 $

Az intervallumgráf egy olyan gráf, melynek csúcsai megfeleltethetőek a valós számok egy-egy intervallumának, és két csúcs között akkor vezet él, ha a nekik megfeleltethető két intervallum metszete nem üres.

Az intervallumgráfok mindig perfekt gráfok.

Egy $G$ gráfot páros gráfnak nevezünk, ha csúcsainak a $V(G)$ halmaza felbontható az $A$ és $B$ diszjunkt részhalmazokra, úgy hogy $A$-n és $B$-n belül nem vezetnek élek.

A páros gráfok kromatikus száma 2, élkromatikus számukra pedig König Dénesnek van egy remek tétele:

Ha $G$ páros gráf, akkor $ \chi_e(G) = \Delta(G) $

Jan Mycielski lengyel matematikust nyugtalanította az a kérdés, hogy léteznek-e olyan gráfok, amelyeknek a kromatikus száma nagyon nagy, de a klikkszáma csak 2.

Létrehozott egy konstrukciót, amivel olyan gráfokat lehet alkotni, amelyek klikkszáma 2, a kromatikus számuk pedig bármilyen nagy lehet. Ezeket a gráfokat Mycielski-gráfoknak nevezzük.