Otwórz menu główne

Kolorowaniem 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ę -kolorowalnym[1].

Jeżeli wszystkie listy są zbiorami to kolorowanie z listy staje się kolorowaniem w zwykłym sensie[1].

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[1].

Liczba wyborów oznacza najmniejsze takie, że ma poprawne kolorowanie z list niezależnie od tego jakie listy zostaną przypisane jego wierzchołkom[1].

-wybieralność grafu implikuje jego -kolorowalność, ale nie odwrotnie[1].

Definicje formalneEdytuj

L-kolorowalnośćEdytuj

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[1].

k-wybieralnośćEdytuj

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[1].

WłasnościEdytuj

Dla grafu   zachodzi:

  1.  [2].
  2.  [2].
  3. Jeżeli   jest planarny:  [3].
  4. Jeżeli   jest planarny i dwudzielny:  [3]

ZastosowanieEdytuj

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żEdytuj

PrzypisyEdytuj

  1. a b c d e f g Courtney L. Baber: An Introduction to List Colorings of Graphs, Faculty of the Virginia Polytechnic Institute and State University, 2009.
  2. a b Michelle A. Lastrina: List-coloring and Sum-list-coloring problem on graphs, Iowa State University, 2012.
  3. a b Douglas R. Woodall: List colourings of graphs, Surveys in Combinatorics, s. 269–301, 2011.