Gráfok színezése

A Wikipédiából, a szabad enciklopédiából.

Egy 6 pontból álló gráf színezése 3 színnel.

A gráfelméletben gráfok színezésének nevezzük, amikor színeket (vagy számokat) rendelünk egy gráf csúcsaihoz, esetleg éleihez. Ez utóbbit a gráf élszínezésének nevezzük. Az élszínezés tekinthető az élgráf csúcsszínezésének is.

Egy gráf jó színezése csúcsainak olyan színezése, ahol összekötött csúcsok eltérő színeket kapnak.

A szükséges színek számának megállapítása általában NP-nehéz probléma.

Nagyon sok megoldatlan kérdés van a gráfok színezése terén, viszont számtalan érdekes használata is van a gráfszínezésnek. Például az ismert Sudoku játékot is lehet egy gráfnak tekinteni. Itt egy-egy sor, oszlop, és 3*3-as négyzet külön klikkeket alkot, melyben minden szám (szín) csak egyszer szerepelhet.

[szerkesztés] A kromatikus szám

A Petersen-gráf kromatikus száma 3

Egy G gráf kromatikus száma G csúcsai jó színezéséhez szükséges színek minimális száma, jelölése $χ(G)$ .

[szerkesztés] Tulajdonságok

$χ(G) = 1$ akkor és csak akkor ha a gráf független pontokból áll (éleket nem tartalmaz)

$χ(G) = 2$ ha $G$ páros gráf

$χ(G)$ $\geq$ $3$ ha $G$ tartalmaz páratlan kört.

$χ(G)$ $\geq$ $ω(G)$ (ahol $ω(G)$ $G$ klikkszámát jelöli)

Ha $χ(G)$ = $ω(G)$ akkor a gráf perfekt.

$χ(G)$ $\leq$ $Δ(G) + 1$ (ahol $Δ(G)$ $G$ maximális fokszámát jelöli)

$χ(G)$ $\leq$ $Δ(G)$ ha $G$ nem teljes gráf és nem tartalmaz páratlan hosszú kört (Brooks-tétel)

$χ(K n) = n$ ahol $K n$ az $n$ csúcsú teljes gráfot jelöli.

[szerkesztés] Az élkromatikus szám

Egy gráf élkromatikus száma az a minimális érték, ahány színnel ki tudjuk úgy színezni a gráf éleit, hogy tetszőleges két él, melynek egy közös csúcs a végpontja, ne legyen azonos színű. Ez tehát az élgráf kromatikus száma. Az élkromatikus számot $χ e (G)$ -vel jelöljük. A Vizing-tétel a $\chi_e(G)\leq\Delta(G)$ felső korlátot adja meg egy egyszerű, összefüggő gráf élkromatikus számára.