彩色数問題は1972年にリチャード・カープが提案した21のnp完全問題の1つになっており、ほぼ同じころにバックトラッキングやの削除・縮約の繰り返し(deletion-contraction recurrence)などに基づいた指数関数時間の様々なアルゴリズムが開発された。