Graph coloring has been studied as an algorithmic problem since the early 1970s: the chromatic number problem is one of Karp’s 21 NP-complete problems from 1972, and at approximately the same time various exponential-time algorithms were developed based on backtracking and on the deletion-contraction recurrence of Zykov (1949).
Colorarea grafurilor a fost studiată și ca problemă algoritmică încă de la începutul anilor 1970: problema numărului cromatic este una din cele 21 de probleme 21 NP-complete ale lui Karp din 1972, și în aproximativ în același timp au fost dezvoltați diverși algoritmi în timp exponențial pe baza backtrackingului și pe recurența ștergere-contracție a lui Zykov (1949).