Un procedimiento para la construcción de facetas para el poliedro de coloreo de máximo impacto

Abstract

Dados dos grafos G = (V,E_G) y H = (V,E_H) sobre el mismo conjunto de vértices y dado un conjunto de colores C, el impacto sobre H de un coloreo c : V → C de G es el número de aristas ij ∈ E_H tales que c(i) = c(j). El problema de coloreo de máximo impacto solicita un coloreo de G que maximice el impacto sobre H. Este problema surge en el contexto de la asignación de aulas a cursos, cuando es deseable –pero no obligatorio– asignar la misma aula a distintas sesiones de un mismo curso.