Si G=(V, E) es un grafo no dirigido, una coloración propia de G, ocurre cuando coloreamos los vértices de G de modo que si {a, b} es una arista en G entonces a y b tienen diferentes colores (por lo tanto, los vértices adyacentes tienen colores diferentes).