En Teoría de grafos, la coloración de grafos es un caso especial de etiquetado de grafos; es una asignación de etiquetas llamadas colores a elementos del grafo. De manera simple, una coloración de los vértices de un grafo tal que ningún vértice adyacente comparta el mismo color es llamado vértice coloración. Similarmente, una arista coloración asigna colores a cada arista tal que aristas adyacentes no compartan el mismo color, y una coloración de caras de un grafo plano a la asignación de un color a cada cara o región tal que caras que compartan una frontera común tengan colores diferentes. El vértice coloración es el punto de inicio de la coloración, y los otros problemas de coloreo pueden ser transformados a una versión con vértices. Por ejemplo, una arista coloración de un grafo es justamente una vértice coloración del grafo línea respectivo, y una coloración de caras de un grafo plano es una vértice coloración del grafo dual.
La convención de usar colores se origina de la coloración de países de un mapa, donde cada cara es literalmente coloreada. Esto fue generalizado a la coloración de caras de grafos inmersos en el plano. En representaciones matemáticas y computacionales se utilizan típicamente enteros no negativos como colores. En general se puede usar un conjunto finito como conjunto de colores. La naturaleza del problema de coloración depende del número de colores pero no sobre cuales son.
Asignando distintos colores a distintos vértices siempre obtendremos una coloración propia, entonces
{\displaystyle 1\leq \chi (G)\leq n.\,}
El único grafo que es 1-coloreable es el grafo sin aristas, y el grafo completo
{\displaystyle K_{n}\,}
de n vértices requiere
{\displaystyle \chi (K_{n})=n\,}
colores.
Si G contiene un clique de orden k, entonces a lo menos son necesarios k colores para colorear el clique; en otras palabras, el número cromático es a los menos el número de clique:
{\displaystyle \chi (G)\geq \omega (G).\,}
Los grafos 2-coloreables son exactamente grafos bipartitos, incluidos árboles y bosques. Por el teorema de los cuatro colores, todo grafo plano es 4-coloreable.
La arista coloración es una vértice coloración de su grafo lineal, y viceversa. Esto es,
{\displaystyle \chi '(G)=\chi (L(G)).\,}
Existe una fuerte relación entre la arista coloración y el grado máximo del grafo. Como todas las aristas incidentes a algún vértice necesitan colores distintos, tenemos
{\displaystyle \chi '(G)\geq \Delta (G).\,}
Más aún,
Teorema de König: Si
{\displaystyle G\,}
es bipartito entonces
{\displaystyle \chi '(G)=\Delta (G)\,}
Teorema de Vizing (1964):
{\displaystyle \chi '(G)\leq \Delta (G)+1.\,}