Listaszínezés

A K_3,27 teljes páros gráf egy listaszínezése csúcsonként három színnel. A három középső csúcsnak bármilyen színeket is választunk, a külső 27 csúcs valamelyikét nem sikerül majd kiszínezni, amiből sejthető, hogy a K_3,27 listakromatikus száma legalább 4.

A gráfelméletben a listaszínezés a gráfok színezésének egy fajtája, ahol a gráf csúcsaihoz adott elemszámú listákról választott színeket rendelnek. Az 1970-es években egymástól függetlenül 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. Ekkor a listaszínezés olyan kiválasztási függvény, ami minden v csúcsot egy az L(v) listán szereplő színhez rendel. Ahogy a gráfok színezésénél megszokott, a listaszínezésnél is általában a „jó” színezéseket vesszük figyelembe, tehát ahol az egy élre illeszkedő csúcsok nem azonos színűek.

A G gráf $ch(G)$-vel jelölt listakromatikus száma vagy 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.

Egy G gráf pontosan akkor k-listaszínezhető (k-choosable, k-list-colorable), ha a csúcsokhoz k színből álló listák tetszőleges hozzárendeléséhez tartozik jó listaszínezés. A G gráf $ch(G)$-vel jelölt listakromatikus száma vagy listaszínezési száma (choosability, list colorability, list chromatic number) az a legkisebb k pozitív egész szám, amire fennáll, hogy G k-listaszínezhető.

Általánosabban, ha egy f függvény minden v csúcshoz egy f(v) pozitív egész számot rendel, a G gráf f-listaszínezhető, ha létezik listaszínezése, bárhogy is rendelünk minden v csúcshoz egy f(v) színből álló listát. Amennyiben $f(v)=k$ a gráf minden v csúcsára, az f-listaszínezhetőség megegyezik a k-listaszínezhetőséggel.

Tulajdonságok

Egy G gráfra jelölje χ(G) a gráf kromatikus számát, Δ(G) pedig G maximális fokszámát. Ekkor a ch(G) listakromatikus számára a következők igazak.

1. ch(G) ≥ χ(G). Egy k-listaszínezhető gráfnak mindig van olyan listaszínezése, amiben minden csúcshoz ugyanazt a k színből álló listát rendeljük, ami egybeesik a szokásos k-színezéssel.
2. ch(G) nem korlátozott a kromatikus szám függvényében, tehát nincs olyan f függvény, melyre ch(G) ≤ f(χ(G)) tetszőleges G gráfra. Ahogy a teljes páros gráf példája mutatja, léteznek olyan gráfok, melyekben χ(G) = 2 de ch(G) tetszőlegesen nagy.
3. ch(G) ≤ χ(G) ln(n), ahol n a G csúcsainak száma.
4. ch(G) ≤ Δ(G) + 1.
5. ch(G) ≤ 5, ha G síkbarajzolható gráf.
6. ch(G) ≤ 3, ha G páros síkbarajzolható gráf.

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 \mathrm{\Delta }(G)+1$, ahol $\mathrm{\Delta }(G)$ a G gráf maximális fokszámát jelöli.

Bizonyítás: Színezzük a csúcsokat a 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 $\mathrm{\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_{(\genfrac{}{}{0ex}{}{2k-1}{k}),(\genfrac{}{}{0ex}{}{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 $(\genfrac{}{}{0ex}{}{2k-1}{k})$ különböző k elemű lista készíthető, amiket rendeljünk hozzá a $K_{(\genfrac{}{}{0ex}{}{2k-1}{k}),(\genfrac{}{}{0ex}{}{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_{(\genfrac{}{}{0ex}{}{2k-1}{k}),(\genfrac{}{}{0ex}{}{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(c)=L(f):=\{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 Fred 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 (L(G))$.

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

Kapcsolódó szócikkek

• Dinitz-probléma
• Lista-élszínezés

Források

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