Colorear vértices de modo que los que estén unidos tengan colores distintos.
La coloración de grafos es un concepto fundamental en la teoría de grafos que trata sobre asignar etiquetas, que normalmente llamamos "colores", a los elementos de un grafo siguiendo ciertas reglas. La forma más común es la coloración de vértices, donde asignas colores a los vértices de tal manera que no haya dos vértices adyacentes con el mismo color. El objetivo principal suele ser minimizar la cantidad de colores que usas. Al número más pequeño de colores necesarios para colorear un grafo $G$ lo llamamos número cromático, y lo escribimos como $\chi(G)$. Este concepto también se aplica a la coloración de aristas (donde asignas colores a las aristas para que no haya dos que compartan un vértice con el mismo color) y a la coloración de caras en grafos planos.
En las matemáticas de olimpiada, la coloración de grafos es una herramienta súper potente para problemas de particiones y para analizar conflictos. Se usa mucho para modelar problemas de horarios (donde las aristas representan conflictos de tiempo), asignación de registros en computación y para colorear mapas. Además de modelar directamente, los argumentos de coloración sirven mucho como técnica de demostración para resultados de imposibilidad. Por ejemplo, si un problema de teselado se puede representar con un grafo que requiere 3 colores, pero una restricción local te obliga a usar solo 2, llegas a una contradicción.
La intuición del número cromático depende mucho