Viršūnių spalvinimas

Peterseno grafas, kurio viršūnės nudažytos trimis spalvomis

Viršūnių spalvinimas (angl. vertex coloring) - grafo spalvinimo variantas, kai grafo viršūnėms priskiriamos spalvos taip, kad gretimos viršūnės turėtų skirtingas spalvas.

Chromatinis skaičius

Mažiausias skaičius spalvų, kuriomis galima nudažyti grafo viršūnes, vadinamas grafo chromatiniu skaičiumi.

Esama įvairių grafo chromatinio skaičiaus įverčių. Pavyzdžiui, keturių spalvų teorema teigia, kad plokščiojo grafo chromatinis skaičius neviršija keturių.

Algoritmai

Bendru atveju patikrinti, ar n viršūnių turintis grafas gali būti nudažytas k spalvų galima peržiūrint visus derinius iš n elementų po k (kiekvienai viršūnei priskiriama viena iš k spalvų). Ieškant chromatinio skaičiaus tokius patikrinimus reikia atlikti k reikšmėms nuo 1 iki n, tad algoritmo laikinis sudėtingumas yra $O((n+1)!)$.

Kadangi tikslus algoritmas yra lėtas, paprastai naudojami euristiniai algoritmai.