Najmniejszym dość trudnym grafem jest ścieżka
Algorytm SL (smallest last) Algorytm SL wygląda następująco: Znajdź wierzchołek o minimalnym stopniu i usuń go z grafu. Powtarzaj krok pierwszy tak długo, aż graf będzie pusty (zapamiętaj kolejność usuwanych wierzchołków). Koloruj wierzchołki zachłannie, zgodnie z ustaloną wcześniej kolejnością (zaczynając od wierzchołków usuniętych później).
Algorytm SL jest statyczny, jego złożoność wynosi gdzie – liczba wierzchołków, – liczba krawędzi.
Algorytm SLF (saturated largest first) Kolorowanie grafu przy pomocy algorytmu SLF polega na wykonaniu poniższych czynności:
dopóki istnieją niepokolorowane wierzchołki wykonuj operacje: { znajdź wierzchołek o maksymalnym stopniu spośród wierzchołków o maksymalnym stopniu nasycenia pokoloruj znaleziony wierzchołek zachłannie
Stopniem nasycenia wierzchołka nazwiemy tu liczbę różnych kolorów sąsiednich z tym wierzchołkiem.