Listaszínezés

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

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

Definíció[szerkesztés]

Egy G gráf minden csúcsához legyen adott egy 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 minden -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 -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 listákat, amikre teljesül, G színezhető lesz az adott listákról.

Listaszínezési tételek[szerkesztés]

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[szerkesztés]

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[szerkeszté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[szerkesztés]

Tétel: Ha G páros gráf, akkor .

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

Külső hivatkozások[szerkesztés]

Lábjegyzetek[szerkesztés]

  1. Vizing, V. G. (1976). Vertex colorings with given colors (in Russian). Metody Diskret. Analiz. 29, 3–10.
  2. Erdő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.
  3. Gutner, Shai (1996). The complexity of planar graph choosability. Discrete Math. 159(1):119–130.
  4. Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. ISBN 0-471-02865-7.

Forrás[szerkesztés]

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