Том 11, серия 1, номер 2, 2004 г., Стр. 18-31

УДК 519.1
В. Г. Визинг
Факторная раскраска ребер мультиграфа

Аннотация:
Вводится понятие $k$-факторной раскраски ребер мультиграфа, являющееся обобщением правильной раскраски ребер графа. При $k$-факторной раскраске требуется, чтобы каждой вершине было инцидентно не более $k$ ребер, окрашенных одним и тем же цветом. Исследуется вопрос о минимальном числе цветов, необходимых для $k$-факторной раскраски всех ребер мультиграфа. Даются неулучшаемые верхние оценки при нечетных $k\geqslant 3$. Основные результаты справедливы и для раскраски в предписанные цвета.

Визинг В. Г. ¹
1. ул. Варненская, 18/2, кв. 26
65070 Одесса, Украина
е-mail: vizing@paco.net

Статья поступила 1 декабря 2003 г.