Kolorowanie grafu – zagadnienie powszechnie występujące w matematycznej teorii grafów. Polega ono w ogólności na przypisaniu określonym elementom składowym grafu (najczęściej jego wierzchołkom; rzadziej krawędziom lub ścianom) wybranych kolorów według ściśle określonych reguł. Klasyczne (czyli wierzchołkowe) kolorowanie grafu jest związane z przypisaniem wszystkim wierzchołkom w grafie jednej z wybranych barw w ten sposób, aby żadne dwa sąsiednie wierzchołki nie miały tego samego koloru. Innymi słowy, pewne pokolorowanie wierzchołkowe jest poprawne (legalne, dozwolone) wtedy, gdy końcom żadnej krawędzi nie przypisano tego samego koloru.
Podstawowe definicje Kolorowanie wierzchołków grafu (kolorowanie wierzchołkowe) – przyporządkowywanie wierzchołkom grafu liczb naturalnych w taki sposób, aby końce żadnej krawędzi nie miały przypisanej tej samej liczby. Ze względów historycznych oraz dla lepszego zobrazowania problemu mówi się o kolorowaniu, przy czym różnym kolorom odpowiadają różne liczby.
Uwaga. W matematyce rozważa się również kolorowanie krawędzi grafu (kolorowanie krawędziowe).
Pokolorowaniem wierzchołków grafu nazywamy jedno konkretne przyporządkowanie kolorów wierzchołkom.