Kolorowanie z list – takie kolorowanie grafu w którym każdy z wierzchołków tego grafu otrzymuje listę kolorów które mogą zostać mu przypisane. Jeżeli istnieje wtedy poprawne kolorowanie, to graf nazywa się -kolorowalnymCourtney L. Baber: An Introduction to List Colorings of Graphs, Faculty of the Virginia Polytechnic Institute and State University, 2009..
Jeżeli wszystkie listy są zbiorami to kolorowanie z listy staje się kolorowaniem w zwykłym sensie.
Graf nazywa się -wybieralnym jeżeli dla każdego wierzchołka przypisana mu lista kolorów jest długości a graf ma legalne kolorowanie z listy.
Liczba wyborów oznacza najmniejsze takie, że ma poprawne kolorowanie z list niezależnie od tego jakie listy zostaną przypisane jego wierzchołkom.
-wybieralność grafu implikuje jego -kolorowalność, ale nie odwrotnie.
Definicje formalne L-kolorowalność Niech będzie zbiorem kolorów, dla każdego niech będzie funkcją przypisującą każdemu wierzchołkowi listę kolorów Jeżeli istnieje funkcja taka, że dla każdego oraz dla wtedy nazywa się -kolorowalnym.
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