Dados dos grafos G = (V,EG) y H = (V,EH) 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 ∈ EH 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.