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–TaylorErdős, P.; Rubin, A. L.; Taylor, H. (1979). Choosability in graphs . In Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata, Congr. Num. 26, 125–157.Gutner, Shai (1996). The complexity of planar graph choosability. Discrete Math. 159(1):119–130.Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. . vezette be.
Definíció Egy G gráf minden csúcsához legyen adott egy 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 -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 listákat, amikre 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 -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 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. 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. 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.. ch(G) ≤ χ(G) ln(n), ahol n a G csúcsainak száma. ch(G) ≤ Δ(G) + 1. ch(G) ≤ 5, ha G síkbarajzolható gráf. 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 , ahol 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 legyen ahhoz, hogy a gráf színezhető legyen az adott listákról.
Tétel: Tetszőleges G gráfra , ahol 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 , ha minden listán legalább eggyel több szín van, akkor az eljárás végigfut.
Tétel: Minden pozitív egészhez létezik olyan G páros gráf, amire .
Bizonyítás: Tekintsük a 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 különböző k elemű lista készíthető, amiket rendeljünk hozzá a 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 nem színezhető az adott listákról.
Példa
thumb| teljes páros gráf
Tekintsünk egy több szempontból is nevezetes gráfot, -at!
Állítás:
Bizonyítás: Megmutatjuk, hogy alkalmas választással adhatók 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: , , . 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 .
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 .
Megjegyzés: L(G) jelöli a G gráf élgráfját.
Jegyzetek
Források BME Kombinatorika és gráfelmélet 2. című tárgy előadásai
Kapcsolódó szócikkek Dinitz-probléma Lista-élszínezés
Kategória:Gráfok színezése