Listaszínezés

Egy G gráf minden ${\displaystyle v\in V(G)}$  csúcsához legyen adott egy ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle L(v)}$  listákat, amikre ${\displaystyle L(v)\geq 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 ${\displaystyle 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 ${\displaystyle f(v)=k}$  a gráf minden v csúcsára, az f-listaszínezhetőség megegyezik a k-listaszínezhetőséggel.

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.^[5]
3. ch(G) ≤ χ(G) ln(n), ahol n a G csúcsainak száma.^[6][7]
4. ch(G) ≤ Δ(G) + 1.^[1][2]
5. ch(G) ≤ 5, ha G síkbarajzolható gráf.^[8]
6. ch(G) ≤ 3, ha G páros síkbarajzolható gráf.^[9]

Tétel: Tetszőleges G gráfra igaz, hogy a ${\displaystyle ch(G)\geq \chi (G)}$ , ahol ${\displaystyle \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 ${\displaystyle \chi (G)}$  legyen ahhoz, hogy a gráf színezhető legyen az adott listákról.

Tétel: Tetszőleges G gráfra ${\displaystyle ch(G)\leq \Delta (G)+1}$ , ahol ${\displaystyle \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 ${\displaystyle \Delta (G)}$ , ha minden listán legalább eggyel több szín van, akkor az eljárás végigfut.

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

Bizonyítás: Tekintsük a ${\displaystyle 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 ${\displaystyle {\binom {2k-1}{k}}}$  különböző k elemű lista készíthető, amiket rendeljünk hozzá a ${\displaystyle 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 ${\displaystyle K_{{\binom {2k-1}{k}},{\binom {2k-1}{k}}}}$  nem színezhető az adott listákról.

 

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

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

Bizonyítás: Megmutatjuk, hogy alkalmas választással adhatók ${\displaystyle 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: ${\displaystyle L(a)=L(d):=\{1,2\}}$ , ${\displaystyle L(b)=L(e):=\{1,3\}}$ , ${\displaystyle 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.

Sejtés: Ha G élgráf, akkor ${\displaystyle 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.

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

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

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

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