Graafi värvimine

Graafiteoorias on graafi värvimine graafi elementide sildistamine (tavaliselt värvidega) teatud reeglite alusel.

pisi|Ühe graafi kõik 12 võimalikku värvimist 3 värviga

Graafi tippude värvimisel antakse igale tipule värv nii, et ühelgi naabertipul poleks sama värv. Graafi kromaatiline arv on minimaalne arv värve, mis on tippude värvimiseks vajalikud.

Graafi servade värvimisel antakse igale servale värv nii, et ühise tipuga servadel poleks sama värv. Graafi servade värvimine on analoogne selle graafi servagraafi tippude värvimisega.

Vaata ka
Neljavärviprobleem

Kategooria:Graafiteooria