Pokolorowanie jest legalne (dozwolone), gdy końcom żadnej krawędzi nie przyporządkowano tego samego koloru.
Optymalnym pokolorowaniem danego grafu nazywamy legalne pokolorowanie zawierające najmniejszą możliwą liczbę kolorów.
Liczbą chromatyczną grafu nazywamy liczbę równą najmniejszej możliwej liczbie kolorów potrzebnych do legalnego pokolorowania wierzchołków grafu
Algorytmy kolorowania grafów Ze względu na bardzo szerokie zastosowania, kolorowanie grafów jest przedmiotem rozległych badań. Problem znalezienia optymalnego pokolorowania, a także znalezienia liczby chromatycznej jest NP-trudny. Z tego względu do kolorowania dużych grafów nadają się jedynie algorytmy przybliżone.
Algorytm LF (largest first) Kolorowanie grafu za pomocą algorytmu LF można opisać następująco: Uporządkuj wierzchołki grafu malejąco według ich stopni (liczby krawędzi z nich wychodzących). Koloruj wierzchołki zachłannie, zgodnie z ustaloną wcześniej kolejnością (zaczynając od wierzchołka o największym stopniu).
Algorytm LF jest algorytmem statycznym, gdyż raz ustalona kolejność wierzchołków nie zmienia się w trakcie jego działania.