Об одном алгоритме раскраски ребер мультиграфов

Пусть $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.