The search for minimal edge $1$-extension of an undirected colored graph

Граф $G=(V, \alpha, f)$ — это цветной граф с определенной на множестве его вершин функцией раскраски $f$. Цветной граф $G^*$ называется реберным $1$-расширением цветного графа $G$, если граф $G$ можно вложить с учетом цветов в каждый граф, получающийся из графа $G^*$ удалением любого его ребра. Реберное $1$-расширение $G^*$ графа $G$ называется минимальным, если граф $G^*$ имеет столько же вершин, сколько содержит исходный граф $G$, а среди всех реберных $1$-расширений графа $G$ граф $G^*$ имеет минимальное число ребер. Рассматривается задача поиска минимальных реберных $1$-расширений цветного графа без проверки на изоморфизм. Предлагается алгоритм поиска множества всех неизоморфных минимальных $1$-расширений для заданного цветного графа.