RUS  ENG
Полная версия
ЖУРНАЛЫ // Прикладная дискретная математика // Архив

ПДМ, 2011, номер 3(13), страницы 85–91 (Mi pdm338)

Эта публикация цитируется в 1 статье

Прикладная теория графов

Интервальная на одной доле правильная реберная 5-раскраска двудольного графа

A. M. Магомедов, Т. А. Магомедов

Дагестанский государственный университет, г. Махачкала, Россия

Аннотация: Пусть в двудольном графе $G=(X,Y,E)$ степень каждой вершины в $X$ равна 2, наибольшая степень вершины в $Y$ равна 5. Найдены условия существования правильной рёберной 5-раскраски графа $G$, интервальной на множестве $X$.

Ключевые слова: двудольный граф, $NP$-полнота, рёберная раскраска.

УДК: 519.1+519.8



© МИАН, 2024