Pemberian warna kepada setiap simpul suatu graf. Pewarnaan simpul disebut tepat jika simpul-simpul yang bertetangga selalu diberi warna berbeda.