Том 7, серия 1, номер 3, 2000 г., Стр. 72-85

УДК 519.174
В. А. Ташкинов
Об одном алгоритме раскраски рёбер мультиграфов

Аннотация:
Пусть $n(G)$, $m(G)$, $\Delta(G)$ и $q(G)$ обозначают соответственно число вершин, число ребер, максимальную степень вершин и хроматический класс мультиграфа $G$. М. К. Гольдберг предположил, что существует эффективный алгоритм раскраски ребер произвольного мультиграфа $G$ в $\max\{q(G),\Delta(G)+1\}$ цветов. Он же предположил, что для любого мультиграфа $G$ с хроматическим классом $q(G)>\Delta(G)+1$ справедливо равенство
$$ q(G)=\max_{H\subseteq G}\left\lceil\frac{m(H)}{\lfloor\frac{n(H)}2\rfloor}\right\rceil. $$
Т. Нишизеки и К. Кашиваги доказали это равенство для мультиграфов с $q(G)>\frac{11\Delta(G)+8}{10}$ при помощи эффективного алгоритма раскраски ребер произвольного мультиграфа $G$ в $\max\{q(G),\lfloor\frac{11\Delta(G)+8}{10}\rfloor\}$ цветов. В данной статье строится простой эффективный алгоритм раскраски ребер произвольного мультиграфа, с помощью которого дается более короткое доказательство этих результатов.
Библиогр. 7.

Ташкинов В. А. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 19 апреля 2000 г.