Una -coloración de un Grafo es una función de etiquetado tal que para todo par de vértices adyacentes , se cumple que . Esto asegura que todos los vértices adyacentes sean asignados a elementos distintos del conjunto . A la imagen de un vértice se le conoce como el color de bajo .
En particular, los grafos que permiten una bicoloración también se conocen como Grafos bipartitos.