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)\ne 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)⩽{\chi }_L(G)$.
2. ${\chi }_L(G)⩽\mathrm{\Delta }(G)+1$.
3. Jeżeli $G$ jest planarny: ${\chi }_L(G)⩽5$.
4. Jeżeli $G$ jest planarny i dwudzielny: ${\chi }_L(G)⩽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