Kolorowanie z list

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

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

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

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

$k$-wybieralność grafu implikuje jego $k$-kolorowalność, ale nie odwrotnie.

Definicje formalne

L-kolorowalność

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

k-wybieralność

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

Własności

Dla grafu $G$ zachodzi:

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

Zastosowanie

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ą.

Zobacz też

• kolorowanie grafu
• multikolorowanie grafu