Известия Саратовского университета. Новая серия.
ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


минимальные расширения

О поиске минимальных реберных 1-расширений неориентированного цветного графа

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