k-wybieralność Jeżeli jest liczbą naturalną, funkcja jest taka, że dla każdego a graf ma legalne kolorowanie z listy, wtedy mówi się, że jest -wybieralny, oraz definiuje się liczbę wyborów, jako najmniejsze takie, że ma poprawne kolorowanie z list niezależnie od tego jakie listy zostaną przypisane jego wierzchołkom.
Własności Dla grafu zachodzi:
Michelle A. Lastrina: List-coloring and Sum-list-coloring problem on graphs, Iowa State University, 2012.. . Jeżeli jest planarny: Douglas R. Woodall: List colourings of graphs, Surveys in Combinatorics, s. 269–301, 2011.. Jeżeli jest planarny i dwudzielny:
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
Przypisy
Kategoria:Teoria grafów