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 A ch′(G) néhány tulajdonsága: ch′(G) < 2 χ′(G). ch′(Kn,n) = n. Ez a Dinitz-sejtés, amit bizonyított. ch′(G) < (1 + o(1))χ′(G), tehát a lista-élkromatikus szám és az élkromatikus szám aszimptotikusan megegyeznek . 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 A lista-élszínezéssel kapcsolatos leghírhedtebb nyitott kérdés a lista-élszínezési sejtés.
ch′(G) = χ′(G).
Fordítás
Jegyzetek . .
Kategória:Gráfok színezése