RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., сер. 1, 2004, том 11, выпуск 2, страницы 18–31 (Mi da101)

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

Факторная раскраска ребер мультиграфа

В. Г. Визинг


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

УДК: 519.1

Статья поступила: 01.12.2003



Реферативные базы данных:


© МИАН, 2024