Coloraciones robustas

Ponente(s): Nadia Guadalupe Vasquez Martinez, Gabriela Judith Blanco Rodríguez Kevin Axel Prestegui Ramos

Una coloración robusta busca la k-coloración válida de mínima rigidez. Se distingue del problema de coloración mínima, porque permite obtener soluciones donde no sólo es importante encontrar soluciones válidas, sino también que sean estables. Nos vamos a enfocar principalmente en graficas cíclicas y que sean impares, ya que se compartan de manera distinta que las pares, tomaremos algunos casos, el primero seria cuando el numero cromático es 3 y el salto de las aristas va a valer 1, en otro donde los pesos de las aristas dependan del salto con 3 y 4 colores, y finalmente donde la función de pesos asigna 2 a aquellas aristas entre vértices a distancia 2 y 3 y veremos cómo se relaciona la rigidez de dicha gráfica con una función de asignación constante 1.