Listaszínezés

A gráfelméletben a listaszínezés a gráfok színezésének egy fajtája, ahol a gráf csúcsait egy adott elemszámú listákról színezzük. Az úgynevezett listaszínezési számot (choice number) először Vizing és Erdős-Rubin-Taylor. vezette be.

Definíció

Egy G gráf minden $v\in V(G)$ csúcsához legyen adott egy $L(v)$ színlista. G színezhető az adott listákról, ha van a csúcsoknak olyan jó színezése, ahol a v csúcs színére fennáll, hogy $c(v)\in L(v)$ minden $v \in V(G)$-re. (Jó színezésről akkor beszélünk, ha az egy élre illeszkedő csúcsok nem azonos színűek.)

A G gráf $ch(G)$-vel jelölt listaszínezési száma az a legkisebb k pozitív egész szám, amire fennáll, hogy akárhogyan adunk meg a csúcsokhoz olyan $L(v)$ listákat, amikre $L(v) \ge k$ teljesül, G színezhető lesz az adott listákról.

Listaszínezési tételek

Tétel: Tetszőleges G gráfra igaz, hogy a $ch(G)\ge \chi (G)$, ahol $\chi (G)$ a G gráf kromatikus száma.

Bizonyítás: Ha minden lista azonos az éppen azt jelenti, hogy G színezhető annyi színnel, amennyi a listákon szerepel. Ebből adódik, hogy egyforma listák esetén a listaméret legalább $\chi (G)$ legyen ahhoz, hogy a gráf színezhető legyen az adott listákról.

Tétel: Tetszőleges G gráfra $ch(G) \le \Delta (G) +1$, ahol $\Delta (G)$ a G gráf maximális fokszámát jelöli.

Bizonyítás: Színezzük a csúcsokat mohó algoritmus segítségével. Ezt olyan módon tehetjük meg, hogy egy adott csúcs listájáról tetszőlegesen választunk egy olyan színt, amely a szomszédságában még nem fordult elő. Mivel minden csúcs szomszédsága legfeljebb $\Delta (G)$, ha minden listán legalább eggyel több szín van akkor az eljárás végigfut.

Tétel: Minden $k \ge 2$ pozitív egészhez létezik olyan G páros gráf, amire $ch(G)> k$.

Bizonyítás: Tekintsük a $G=K_{\binom{2k-1}{k}, \binom{2k-1}{k}}$ teljes páros gráfot! Megmutatjuk, hogy megadhatók olyan k elemű listák, amikről választva G nem színezhető jól. Vegyük a színeknek egy 2k-1 elemű halmazát, amelyekből pontosan $\binom{2k-1}{k}$ különböző k elemű lista készíthető, amiket rendeljünk hozzá a $K_{\binom{2k-1}{k}, \binom{2k-1}{k}}$ gráf mindkét színosztályának pontosan egy csúcsához. Most megmutatjuk, hogy ezen listákról nem adható a gráf csúcsainak jó színezése. Indirekt tegyük fel, hogy mégis létezik jó színezés. Ekkor a gráf csúcsainak egyik maximális független halmazának színezésében legalább k színt kellett használnunk, hiszen ha legfeljebb (k-1)-et használtunk volna, akkor lenne k olyan szín, amelynek egyikét sem használtuk itt, azonban ez a k szín éppen az adott független halmaz egyik pontjához rendelt színlista k eleme, így a pontot nem színezhettük volna szabályosan. Ugyanígy a másik maximális független halmazra. Mivel a két független halmaz között minden lehetséges él be van húzva, ezért legalább 2k különböző színük kellene legyen. Ez azonban nem lehetséges, mert feltettük, hogy 2k-1 különböző színünk van. Így $K_{\binom{2k-1}{k}, \binom{2k-1}{k}}$ nem színezhető az adott listákról.

Példa

$K_{3,3}$ teljes páros gráf

Tekintsünk egy több szempontból is nevezetes gráfot $K_{3,3}$-at!

Állítás: $ch(K_{3,3}) > \chi (K_{3,3})$

Bizonyítás: Megmutatjuk, hogy alkalmas választással adhatók $K_{3,3}$ csúcsainak olyan listák, amelyekről a gráf nem színezhető jól. Esetünkben legyenek a csúcsok a, b, c, d, e, f, ahol a, b, c és d, e, f alkossa a két színosztályát a gráfnak. A listák legyenek: $L(a)=L(d):={1,2}$, $L(b)=L(e):={1,3}$, $L(b)=L(e):={2,3}$. Próbáljuk színezni a gráfot a fenti listák segítségével. Feltehetjük, hogy a színe 1 lesz. Ekkor e csúcs színe 3, továbbá c csúcsé 2. Ekkor azonban d-t már nem tudjuk a-tól és c-től is különbözőre kiszínezni. Ezzel az állítást beláttuk.

Listaszínezési sejtés

Sejtés: Ha G élgráf, akkor $ch(G)= \chi (G)$.

Máig megoldatlan a kérdés, azonban létezik egy speciális esete, amit Galvin bizonyított és tartalmazza az úgynevezett Dinitz-problémát.

Galvin tétele

Tétel: Ha G páros gráf, akkor $ch(L(G))=\chi (G)$

Megjegyzés: L(G) jelöli a G gráf élgráfját.

Külső hivatkozások

• A Dinitz-problémáról (Angolul)

Forrás

BME Kombinatorika és gráfelmélet 2. című tárgy előadásai