Multikolorowanie grafu jest uogólnieniem pojęcia kolorowania grafu. Polega ono na przypisaniu każdemu z wierzchołków grafu ważonego tylu kolorów, ile wynosi waga danego wierzchołka. Multikolorowanie nazywa się poprawnym (dopuszczalnym, legalnym) jeżeli dwa wierzchołki połączone krawędzią nie posiadają tego samego koloruRafał Witkowski: Multikolorowanie grafów, X Międzynarodowe Warsztaty Młodych Matematyków, s. 206–218, 2007..

Multikolorowanie grafu ważonego z wagami wierzchołków równymi 1 jest tym samym, co zwykłe kolorowanie tego grafu.

Problem multikolorowania można przetransportować na problem klasycznego kolorowania grafów. Multikolorowanie grafu ważonego jest tym samym, co zwykłe kolorowanie grafu powstałego z przez zastąpienie każdego wierzchołka kliką o rozmiarze oraz utworzenie krawędzi pomiędzy każdymi dwoma wierzchołkami klik i wtedy i tylko wtedy, gdy wierzchołki i były połączone krawędzią w .

Najmniejszą liczbę kolorów niezbędną do legalnego pokolorowania grafu ważonego nazywa się liczbą multichromatyczną lub ważoną liczbą chromatyczną.