Lista-élszínezés
A matematika, azon belül a gráfelmélet területén a lista-élszínezés (list edge-coloring) olyan gráfszínezés, ami a listaszínezés és az élszínezés kombinációja. A lista-élszínezési probléma egy esete egy gráfból és az egyes éleihez hozzárendelt, megengedhető színek listájából áll. Egy lista-élszínezés az egyes élek színének a megengedett színek közül való kiválasztása; a jó élszínezés során két szomszédos él színe mindig különböző.
Egy G gráf k-lista-élszínezhető (k-edge-choosable), ha a G éleihez k színből álló listák tetszőleges hozzárendeléséhez tartozik jó lista-élszínezés.
A G gráf ch′(G)-vel jelölt lista-élkromatikus száma vagy listakromatikus indexe (edge choosability, list edge colorability, list edge chromatic number vagy list chromatic index) az a legkisebb k pozitív egész szám, melyre G k-lista-élszínezhető. Egy sejtés szerint mindig megegyezik a gráf élkromatikus számával.
Tulajdonságok
szerkesztésA ch′(G) néhány tulajdonsága:
- ch′(G) < 2 χ′(G).
- ch′(Kn,n) = n. Ez a Dinitz-sejtés, amit (Galvin 1995) bizonyított.
- ch′(G) < (1 + o(1))χ′(G), tehát a lista-élkromatikus szám és az élkromatikus szám aszimptotikusan megegyeznek (Kahn 2000).
Itt χ′(G) a G élkromatikus száma, Kn,n pedig megegyező méretű partíciókból álló teljes páros gráf.
Listaszínezési sejtés
szerkesztésA lista-élszínezéssel kapcsolatos leghírhedtebb nyitott kérdés a lista-élszínezési sejtés.
- ch′(G) = χ′(G).
Fordítás
szerkesztés- Ez a szócikk részben vagy egészben a List edge-coloring című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Jegyzetek
szerkesztés- Galvin, Fred (1995), "The list chromatic index of a bipartite multigraph", Journal of Combinatorial Theory, Series B 63: 153–158, DOI 10.1006/jctb.1995.1011.
- Jensen, Tommy R. & Toft, Bjarne (1995), "12.20 List-Edge-Chromatic Numbers", Graph Coloring Problems, New York: Wiley-Interscience, pp. 201–202, ISBN 0-471-02865-7.
- Kahn, Jeff (2000), "Asymptotics of the list chromatic index for multigraphs", Random Structures & Algorithms 17 (2): 117–156, DOI 10.1002/1098-2418(200009)17:2<117::AID-RSA3>3.0.CO;2-9