Numer: 11a/2012 Str. 51
Autorzy: Marek Kubale :
Tytuł: Modele i metody kolorowania grafów. Część II
Streszczenie: Niniejszy artykuł jest drugą 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 różne kryteria i ograniczenia modyfikujące kolorowanie klasyczne. Ponieważ kolorowanie we wszystkich tych odmianach i wariantach jest NP-trudne, podano oszacowania na liczbę chromatyczną (indeks chromatyczny) oraz podano potencjalne zastosowania rozważanych modeli w problemach naukowo-technicznych.
Słowa kluczowe: kolorowanie grafu, liczba chromatyczna, indeks chromatyczny, NP-trudność, algorytm wielomianowy