tytryt

Coloración de vértices
Los algoritmos conocidos para colorear los vértices de un grafo se clasifican en dos grandes grupo:  secuenciales  e independientes. Dada  una  ordenación  de los  vértices  del  grafo, los
algoritmos   secuenciales   asignan   el   mínimo   color   posible   al   siguiente   vértice.   Es   decir,   siqueremos colorear el vértice v, teniendo ordenados numéricamente los colores, asignamos a v
el color más pequeño que no aparece entre los asignados a los vecinos de v ya coloreados. La
ordenación inicial es esencial para colorear con pocos colores.
Los algoritmos “independientes” buscan en primer lugar un conjunto independiente de vértices
I1 de cardinal grande, colorea todos los vértices con el color 1, elimina los vértices de I1 y repiteel proceso en el grafo G­I1, continuando así hasta colorear todos los vértices.
Se presenta un procedimiento secuencial para colorear los vértices de un grafo siguiendo un
orden impuesto a los vértices, usando la menor cantidad de colores posibles. Este algoritmo es
llamado austero (avaricioso, greedy en inglés).

Coloración de aristas
Una coloración de aristas de un grafo G (no necesariamente simple) es una asignación decolores a sus aristas de modo que aristas adyacentes reciban colores distintos. Si se usan k
colores hablaremos de una k­coloración en aristas. Una coloración en las aristas origina una
partición del conjunto de aristas A(G) en las llamadas clases de color de las aristas, cada una
de las cuales consta de todas las aristas de un determinado color. Si G tiene una k­coloraciónen aristas decimos que G es k­coloreable en aristas.
Se llama  índice  cromático  de  G  al mínimo  k  para  el  que  G  es  k­coloreable  en  aristas.
Designaremos a este número con la notación N'(G).
También  es  un  problema  NP­completo  determinar  el índice  cromático  de  un  grafo.  Y los
algoritmos  conocidos   para  colorear  las  aristas  de  un   grafo   siguen   las  mismas  estrategiasdescritas para la coloración de vértices.
Ejemplo:
Consideremos la  tabla de horarios de un liceo. Se puede construir un multigrafo bipartito
tomando como conjunto de vértices V1 a los profesores, y como conjunto de vértices V2 a los
grupos. Por cada clase que un profesor debe dictar a un grupo durante la semana se traza unaarista del profesor al grupo. Supongamos que cada clase dura una hora. Entonces tomemos
como conjunto de colores las horas posibles (por ejemplo lunes de 8 a 9, martes de 11 a 12,
etc.) A cada arista se le debe asignar un horario de modo tal que las que salen de un mismo
profesor tengan horarios diferentes, y las que llegan a un mismo grupo también.
El índice cromático  de este multigrafo  representa la mínima longitud  total de la  tabla  dehorarios (es decir el menor número total de horas ocupadas en la semana)

Coloración de regiones (Relaciones con listas y particiones en bloques)
Una coloración de un grafo G es equivalente a una lista con ciertas restricciones. Supongamos
que V(G)={v1, v2,...,vn}, entonces una coloración usando los k colores C={a1, a2, . . . , ak} es
una lista (n­upla) con repetición (ai1,ai2 , . . . ,ain) tal que si vs y vt son adyacentes entonces
ais҂ait.Dada una coloracion χV(G) → C definimos la relación entre los vértices de G de la siguiente
manera: uRv si χ(u)=χ(v), es decir, dos vértices están relacionados si tienen el mismo color.
Esta es una relación de equivalencia. 
Esta  relación induce una partición sobre el conjunto  V(G)  cuyos bloques son las clases deequivalencia. Cada bloque (clase) está constituido por vértices que tienen el mismo color. Es
importante notar que los vértices que están relacionados no son adyacentes; si dos vértices son
adyacentes se encuentran en bloques (clases) distintos. 
Recíprocamente,  si se particiona el conjunto de vértices de un grafo  G  de  tal manera que
vértices adyacentes  se encuentran en bloques distintos, entonces esta partición induce una...