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 | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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 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 \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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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.

Külső hivatkozások[szerkesztés | forrásszöveg szerkesztése]

Lábjegyzetek[szerkesztés | forrásszöveg szerkesztése]

  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 | forrásszöveg szerkesztése]

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