1) Atribuirea k culori (sau orice marcaje distincte), la nodurile de un grafic. 2) Atribuirea de k culori la marginile un grafic.

A de colorat este un colorat corespunzătoare, în cazul în care nici o două vârfuri adiacente sau marginile au aceeaşi culoare.