Diferencia entre revisiones de «Coloración de grafos»

[[Archivo:Petersen graph 3-coloring.svg|thumb|right|Una coloración de vértices para el [[grafo de Petersen]] utilizando tres colores, el número mínimo posible.]]

En [[Teoría de grafos]], la '''coloración de grafos''' es un caso especial de etiquetado de [[grafo]]s; es una asignación de etiquetas llamadas ''colores'' a elementos del grafo. De manera simple, una coloración de los [[Vértice (teoría de grafos)|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 (teoría de grafos)|arista]] coloración asigna colores a cada arista talque 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]].