W rozdziale omówiono tzw. harmoniczne kolorowanie grafów, które jest odmia-ną klasycznego kolorowania wierzchołków grafów. Podano najważniejsze własno-ści tego sposobu kolorowania grafów i jego potencjalne zastosowanie w radio-komunikacji lotniczej i projektoaniu funkcji mieszających. Podano równieżtzw. algorytm degresywny, który koloruje każdy graf za pomocą liczby kolorównie przekraczającej w dwójnasób harmonicznej liczby...

W pracy rozważamy dwa warianty kolorowania krawędzi grafów prostych i ważonych, mianowicie kolorowania zwarte oraz zwarte cyrkularne. Rozważamy relacje pomiędzy nimi. Dowodzimy, że każdy zewnętrznie planarny graf dwudzielny posiada zwarte pokolorowanie krawędziowe oraz, że problem ten dla grafów ogólnych jest NP-zupełny. Podajemy również wielomianowy 1.5-przybliżony algorytm oraz pseudowielomianowy dokładny algorytm zwartego cyrkularnego...

Niniejszy rozdział omawia kontrastowe kolorowanie grafów. Podana zostałajego definicja i podstawowe własności, zastosowania oraz złożoność oblicze-niowa problemów rozważanych w ramach tej dziedziny.

W klasycznym modelu kolorowania grafów,kolor przydzielany wierzchołkowi jestograniczony przez regułę zakazującą pokolorowania dwóch sąsiednich wierz-chołków tym samym kolorem. Kolorowanie listowe wprowadza dodatkowe ograni-czenie: każdy wierzchołek posiada z góry określony zbiór dopuszczalnych ko-lorów. Rozważamy jak duża może być różnica pomiędzy liczbą chromatyczną ilistową liczbą chromatyczną oraz dla jakich klas grafów...

W pracy rozważany jest rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowe, rozproszone algorytmy kolorowania grafów wraz z dokładną analizą teoretyczną i wynikami eksperymentów obliczeniowych.