Lista kantfärgning

I matematik är listkantfärgning en typ av graffärgning som kombinerar listfärgning och kantfärgning . En instans av ett listkantfärgningsproblem består av en graf tillsammans med en lista över tillåtna färger för varje kant. En listkantfärgning är ett val av en färg för varje kant, från dess lista över tillåtna färger; en färgning är korrekt om inte två intilliggande kanter får samma färg.

En graf G är k -kant-valbar om varje instans av listkantfärgning som har G som sin underliggande graf och som ger minst k tillåtna färger för varje kant av G har en korrekt färg. Kantvalbarheten , eller listkantsfärgbarheten , listkantens kromatiska nummer , eller listkromatiskt index , ch′( G ) i grafen G är det minsta talet k så att G är k -kantvalbar . Det antas att det alltid är lika med det kromatiska indexet .

Egenskaper

Några egenskaper hos ch′( G ):

1. ch′( G ) < 2 χ′( G ).
2. ch′(K _{n , n} ) = n . Detta är Dinitz-förmodan , bevisad av Galvin (1995) .
3. ch′( G ) < (1 + o(1))χ′( G ), dvs listans kromatiska index och det kromatiska indexet överensstämmer asymptotiskt ( Kahn 2000 ).

Här är χ′( G ) det kromatiska indexet för G ; och K _{n , n} , den kompletta tvådelade grafen med lika partituppsättningar .

Lista färggissningar

Det mest kända öppna problemet med listkantfärgning är förmodligen listfärgningsförmodan .

ch′( G ) = χ′( G ).

Denna gissning har ett flummigt ursprung; Jensen & Toft (1995) översikt över dess historia. Dinitz-förmodan, bevisad av Galvin (1995) , är specialfallet med listfärgningsförmodan för de kompletta tvådelade graferna K _{n , n} .

• 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, s. 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