listfärgning

Listfärgning är ett område inom grafteori som studerar färgning av grafers hörn när varje hörn har sina egna tillåtna färger, enligt en lista. Givet en graf G=(V,E) och en lista L:V→P(C) där L(v) är den färguppsättning som får användas för hörnet v, kallas en L-färgning en tilldelning c:V→C där c(v)∈L(v) för alla v och där intilliggande hörn har olika färger.

Ett centralt begrepp är listfärgningen och dess listfärgade tal χ_l(G). χ_l(G) är den minsta talen k så att för varje tilldelning av L med |L(v)|≥k för alla v finns en L-färgning av G. Detta generaliserar vanlig färgning, eftersom χ_l(G)≥χ(G) vanligtvis är sant.

Exempel och egenskaper: för en fullständig graf K_n är χ_l(K_n)=n. För cykler gäller att χ_l(C_{2n})=2 och χ_l(C_{2n+1})=3. Generellt kan χ_l(G) vara mycket större än χ(G); det finns grafklasser där gapet mellan χ_l och χ är oändligt stort.

Viktiga resultat och egenskaper: Planara grafer är 5-choosbara (Thomassen, 1994), medan det finns planara grafer som inte är 4-choosbara (Voigt). Planare 5-choosability är därmed nära optimal. Beskrivningen av χ_l(G) är ofta NP-fullständig för allmänna grafer när listorna ges i förväg, och bestämmandet av χ_l för vissa grafklasser är ett aktivt forskningsområde.

Användningar och närliggande begrepp: listfärgning används i resursfördelning och frekvensplanering där varje nod har begränsade färgalternativ. Relaterade koncept inkluderar online-listfärgning (paint number) och precoloring-extensions.