1) L'assegnazione dei colori k (o eventuali marchi distinti) ai vertici di un grafo. 2) L'assegnazione dei colori k ai bordi di un grafico.

A colorare è una colorazione adeguata se non due vertici adiacenti o bordi hanno lo stesso colore.