No/VOL: 11a/2012 Page no. 51
Authors: Marek Kubale :
Title: Modele i metody kolorowania grafów. Część II
Abstract: 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.
Key words: kolorowanie grafu, liczba chromatyczna, indeks chromatyczny, NP-trudność, algorytm wielomianowy