Considérese el problema de colorear una gráfica con el menor número de colores. Un algoritmo muy sencillo sería simplemente probar todas las coloraciones posibles; sin embargo, esto tomaría tiempo exponencial. Por ejemplo, supóngase que se quieren probar todas las coloraciones posibles con cuatro colores en una gráfica de n vértices. Escójanse un vértice y uno de los cuatro colores para éste. Para el siguiente vértice se tienen otra vez cuatro posibilidades, y así sucesivamente. El número total de posibilidades a explorar es 4n.
Desafortunadamente, para el problema de coloración, no se sabe si existe un algoritmo mejor que éste; se trata de un problema NP-completo (véase el tema 1). No se sabe siquiera si existe un algoritmo eficiente (polinomial) para decidir si un mapa requiere de los cuatro colores, o si se puede colorear con tres. Sin embargo, ya se ha descrito un algoritmo eficiente para cuando no se exige ser tan rigurosos, y es suficiente colorear un mapa con seis colores.
