Numer: 09/2010 Str. 115
Autorzy: Marek Kubale :
Tytuł: Modele i metody kolorowania grafów. Część I
Streszczenie: Niniejszy artykuł jest pierwszą częścią 2-odcinkowego cyklu przeglądowego na temat modeli i metod kolorowania grafów. Przedstawiono w nim najważniejsze, z punktu widzenia zastosowań, modele kolorowania grafów. W szczególności pokazano: (1) co można kolorować w grafie (np. wierzchołki, krawędzie, końcówki, ściany, jednocześnie wierzchołki i krawędzie) oraz (2) jak można kolorować (np. dzielenie kolorów, zawijanie kolorów). Ponieważ kolorowanie we wszystkich tych odmianach i wariantach jest NP-trudne, podajemy oszacowania na liczbę chromatyczną (indeks chromatyczny) oraz podajemy potencjalne zastosowania rozważanych modeli w problemach naukowo-technicznych.
Słowa kluczowe: kolorowanie grafu, liczba chromatyczna, indeks chromatyczny, NP-trudność