Grafo spalvinimas

(Nukreipta iš puslapio Grafo nuspalvinimo uždavinys)
 NoFonti.svg  Šiam straipsniui ar jo daliai trūksta išnašų į šaltinius.
Jūs galite padėti Vikipedijai pridėdami tinkamas išnašas su šaltiniais.

Grafo spalvinimas arba grafo dažymas - grupė grafų teorija uždavinių, kuriuose siekiama grafo elementams priskirti spalvas taip, kad būtų tenkinamos tam tikros sąlygos (paprastai - kad gretimi grafo elementai turėtų skirtingas spalvas). Iš tokių uždavinių dažniausiai naudojamas viršūnių spalvinimas, kai kiekvienai viršūnei priskiriama spalva taip, kad gretimos viršūnės turėtų skirtingas spalvas, kiek rečiau - briaunų spalvinimas, kai spalvos priskiriamos briaunoms.

Peterseno grafas, kurio viršūnės nudažytos trimis spalvomis taip, kad gretimos viršūnės turėtų skirtingas spalvas


Commons-logo.svg