K-coloring

O problema de atribuir uma de 'k' cores a cada vértice de um grafo de tal forma que dois vértices adjacentes não tenham a mesma cor. Determinar se um grafo é k-colorável é um problema NP-completo.