Resumen

Sean G y dos grafos complementarios. Dada una función de penalización en las aristas de , la rigidez de una k-coloración de G se define como la suma de las penalizaciones en las aristas de cuyos vértices incidentes son del mismo color. Con base en la definición anterior, el Problema de Coloración Robusta (PCR) se define como la búsqueda de la k-coloración de rigidez mı́nima. Este trabajo realiza un estudio comparativo de varias técnicas heurísticas: Recocido Simulado, GRASP, y Búsqueda Dispersa. Los resultados aquí presentados son los mejores obtenidos para el PCR.

Palabras clave: coloración de grafos, coloración robusta, heurísticas