Uma coloração é o ato de "pintar" vértices/arestas de maneira que vértices/arestas adjacentes não tenham a mesma cor.

Chamamos de $\chi(G)$ o número de cores de um grafo. 

Chamamos de $k$-coloração, uma coloração com $k$ cores.