COLOREADO DE GRAFOS Y NÚMERO CROMÁTICO

El coloreado de un grafo G = (V, E) es una correspondencia C : V —> S, donde S es un conjunto finito (de "colores") tal que si vw pertenece a E, entonces C(v) != C(w) o dicho de otro modo, no se asigna el mismo color a vértices adyacentes.

El número cromático de G, denotado por x(G), es el menor número de colores que se necesitan para colorear G (es decir, el k más pequeño tal que exista un coloreado C para G y |C(V) | = k).

Se nos da un grafo no dirigido G = (V, E) para colorear y dado G, determinar x(G) (y producir un coloreado óptimo, es decir, uno que sólo use x(G) colores).

Problema de decisión: Dado G y un entero positivo k, ¿existe un coloreado de G que use cuando más k colores? (Si lo hay, decimos que G es k-coloreable).

La estrategia del coloreado secuencial (SC) siempre colorea el siguiente vértice vi, con el color más bajo que sea aceptable (es decir, el color más bajo que no se haya asignado ya a un vértice adyacente a vi).

colorSec(V, E)

{

int c, i;

for (i=1; i <= n; i++)

for (c = 1; c <= n; c++)

Si ningún vértice adyacente a vi tiene el color c:

Colorear vi con c.

break; //Salir del for (c)

//Continuar for (c)

//Continuar for (i)

}

Este algoritmo se puede implementar fácilmente de modo que su complejidad en el peor caso es de O(n^3), pero su comportamiento con un grafo dado depende del ordenamiento de los vértices.