Kolorowanie z list

Kolorowanie z list – takie kolorowanie grafu ${\displaystyle G,}$ w którym każdy z wierzchołków ${\displaystyle v\in V}$ tego grafu otrzymuje listę kolorów ${\displaystyle L(v),}$ które mogą zostać mu przypisane. Jeżeli istnieje wtedy poprawne kolorowanie, to graf ${\displaystyle G}$ nazywa się ${\displaystyle L}$-kolorowalnym^[1].

Jeżeli wszystkie listy są zbiorami ${\displaystyle \{1,2,\dots ,\chi (G)\},}$ to kolorowanie z listy staje się kolorowaniem w zwykłym sensie^[1].

Graf nazywa się ${\displaystyle k}$-wybieralnym jeżeli dla każdego wierzchołka ${\displaystyle v\in V(G)}$ przypisana mu lista kolorów ${\displaystyle L(v)}$ jest długości ${\displaystyle k,}$ a graf ma legalne kolorowanie z listy^[1].

Liczba wyborów ${\displaystyle \chi _{L}(G)}$ oznacza najmniejsze ${\displaystyle k}$ takie, że ${\displaystyle G}$ ma poprawne kolorowanie z list niezależnie od tego jakie listy zostaną przypisane jego wierzchołkom^[1].

${\displaystyle k}$-wybieralność grafu implikuje jego ${\displaystyle k}$-kolorowalność, ale nie odwrotnie^[1].

Niech ${\displaystyle C}$ będzie zbiorem kolorów, dla każdego ${\displaystyle v\in V(G)}$ niech ${\displaystyle L:V(G)\to 2^{C}}$ będzie funkcją przypisującą każdemu wierzchołkowi ${\displaystyle v\in V(G)}$ listę kolorów ${\displaystyle L(v)\subseteq C.}$ Jeżeli istnieje funkcja ${\displaystyle f:V(G)\to C}$ taka, że ${\displaystyle f(v)\in L(v)}$ dla każdego ${\displaystyle v\in V(G)}$ oraz ${\displaystyle f(u)\neq f(v)}$ dla ${\displaystyle u,v\in E(G),}$ wtedy ${\displaystyle G}$ nazywa się ${\displaystyle L}$-kolorowalnym^[1].

Jeżeli ${\displaystyle k}$ jest liczbą naturalną, funkcja ${\displaystyle L}$ jest taka, że ${\displaystyle |L(v)|=k}$ dla każdego ${\displaystyle v\in V(G),}$ a graf ${\displaystyle G}$ ma legalne kolorowanie z listy, wtedy mówi się, że ${\displaystyle G}$ jest ${\displaystyle k}$-wybieralny, oraz definiuje się liczbę wyborów, ${\displaystyle \chi _{L}(G)}$ jako najmniejsze ${\displaystyle k}$ takie, że ${\displaystyle G}$ ma poprawne kolorowanie z list niezależnie od tego jakie listy zostaną przypisane jego wierzchołkom^[1].

Dla grafu ${\displaystyle G}$ zachodzi:

1. ${\displaystyle \chi (G)\leqslant \chi _{L}(G)}$^[2].
2. ${\displaystyle \chi _{L}(G)\leqslant \Delta (G)+1}$^[2].
3. Jeżeli ${\displaystyle G}$ jest planarny: ${\displaystyle \chi _{L}(G)\leqslant 5}$^[3].
4. Jeżeli ${\displaystyle G}$ jest planarny i dwudzielny: ${\displaystyle \chi _{L}(G)\leqslant 3}$^[3]

Kolorowanie z list ma zastosowanie w problemie przydziału częstotliwości w sieciach telefonów komórkowych. Każdy nadajnik ma ograniczoną liczbę używanych częstotliwości, a dwa nadajniki będące w swoim zasięgu nie mogą korzystać z tej samej częstotliwości ze względu na zakłócenia. Da się ten problem przedstawić grafowo w następujący sposób: nadajniki są reprezentowane przez wierzchołki grafu, lista częstotliwości danego nadajnika jest listą kolorów odpowiadającego mu wierzchołka. Ponadto jeżeli nadajniki są w swoim wzajemnym zasięgu, odpowiadające im wierzchołki są połączone krawędzią.

• kolorowanie grafu
• multikolorowanie grafu