1) A atribuição de cores (ou quaisquer marcas distintas) para os vértices de um grafo. 2) A atribuição de cores para as arestas de um grafo.

A coloração é uma coloração adequada, se não dois vértices adjacentes ou bordas têm a mesma cor.