Coloreo de Grafos es la coloración de los vértices de un grafo tal que ningún vértice adyacente comparta el mismo color.
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 primer resultado acerca de la coloración de grafos trataba exclusivamente sobre grafos planos y la coloración de mapas. Mientras intentaba colorear un mapa de Inglaterra, Francis Guthrie postulo la teoría de los 4 colores, notando que 4 colores son suficientes para colorear el mapa tal que regiones que comparten un borde común no reciban el mismo color.
Las etiquetas como rojo o azul son solamente utilizadas cuando el número de colores es pequeño, y normalmente los colores están representados por los enteros {1, 2, 3, …}.
Una coloración que usa a lo más k colores se llama k-coloración (propia). El menor número de colores necesarios para colorear un grafo G se denota número cromático . Un grafo que puede ser asignada una k-coloración (propia) es k-coloreable y es k-cromático si su número cromático es exactamente k. Un subconjunto de vértices asignados con el mismo color se llama una clase de color. Cada clase forma un conjunto independiente. Esto es, una k-coloración es lo mismo que una partición del conjunto de vértices en k conjuntos independientes, y los términos k-partito y k-coloreable tienen el mismo significado.
El polinomio cromático cuenta el número de maneras en las cuales puede ser coloreado un grafo usando no más que un número de colores dado
Un algoritmo simple para colorear gráfico es fácil de describir, pero potencialmente muy costosa.
En términos de complejidad computacional - NP-completo Lo que eso significa que no existe algoritmo conocido para colorear gráfica óptima que no es exponencial, y que, además, si hubiera un algoritmo no-exponencial para ella, no sería una solución no-exponencial de todos problemas.
Una solución general a la búsqueda de una coloración gráfica óptimo es la búsqueda exhaustiva: empezar con un nodo, dale un color, asignar colores que no sean contradictorias con sus vecinos, y así sucesivamente. Prueba con dos colores, si no se obtiene ningún resultado, a continuación, intente con tres, y así sucesivamente.
Ejemplos de coloreo de grafos:
Grafo de Petersen con 3 colores; comúnmente dibujado como un pentágono con una estrella de cinco puntas adentro:
---------
----------
Bibliografia.
http://es.wikipedia.org/wiki/Coloraci%C3%B3n_de_grafos
http://scienceblogs.com/goodmath/2007/06/graph_coloring_algorithms_1.php
