Listaszínezés

A Wikipédiából, a szabad enciklopédiából
A K3,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 K3,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[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. 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[szerkesztés]

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.[2][1]
  5. ch(G) ≤ 5, ha G síkbarajzolható gráf.[8]
  6. ch(G) ≤ 3, ha G páros síkbarajzolható gráf.[9]

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.

Kapcsolódó szócikkek[szerkesztés]

Lábjegyzetek[szerkesztés]

  1. ^ a b Vizing, V. G. (1976), "Vertex colorings with given colors", Metody Diskret. Analiz. 29: 3–10
  2. ^ a b 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.
  5. Gravier, Sylvain (1996), "A Hajós-like theorem for list coloring", Discrete Mathematics 152 (1-3): 299–302, DOI 10.1016/0012-365X(95)00350-6.
  6. Eaton, Nancy (2003), On two short proofs about list coloring - Part 1, <http://www.math.uri.edu/~eaton/TalkUriOct03P1.pdf>. Hozzáférés ideje: May 29, 2010
  7. Eaton, Nancy (2003), On two short proofs about list coloring - Part 2, <http://www.math.uri.edu/~eaton/TalkUriOct03P2.pdf>. Hozzáférés ideje: May 29, 2010
  8. Thomassen, Carsten (1994), "Every planar graph is 5-choosable", Journal of Combinatorial Theory, Series B 62: 180–181, DOI 10.1006/jctb.1994.1062
  9. Alon, Noga & Tarsi, Michael (1992), "Colorings and orientations of graphs", Combinatorica 12: 125–134, DOI 10.1007/BF01204715

Forrás[szerkesztés]

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