Algorithms for the coloring of weighted graphs

W pracy zostały zebrane znane wyniki trudności problemu max-kolorowania dla różnych klas grafów. Głównym celem jest zbadanie problemu max-kolorowania w środowisku on-line. Na początku pokazujemy, że nie istnieje algorytm zachłanny o stałym współczynniku kompetytywności.Następnie wprowadzamy problem 2-max-kolorowania, w którym dopuszczamy tylko dwie różne wagi wierzchołków. Pokazujemy, że dla grafów przedziałowych złota liczba jest dolnym ograniczeniem na współczynnik kompetytywności. Przedstawiamy również framework, który pozwala na uzyskiwanie kompetytywnych algorytmów dla 2-max-kolorowania z algorytmów kolorowania on-line. Zastosowanie tego schematu do klasy grafów dziedzicznych pozwala uzyskiwać algorytmy o współczynniku (c*fi) gdzie c jest współczynnikiem kompetytywności algorytmu kolorowania on-line, a fi złotą liczbą.Na koniec prezentujemy framework, który prowadzi do kompetytywnych algorytmów dla max-kolorowania on-line liniowo chi-ograniczonych dziedzicznych klas grafów. Stosujemy go dla kilku podklas grafów doskonałych w tym dla grafów przedziałowych gdzie otrzymujemy następujące algorytmy: 4-kompetytywny dla porządku up-growing z reprezentacją, 8-kompetytywny dla porządku up-growing bez reprezentacji i 12-kompetytywny w przypadku ogólnym. Uzyskujemy również 18-kompetytywny algorytm dla grafów łukowych.