Том 21, номер 4, 2014 г., Стр. 33-41

УДК 519.718
Визинг В. Г.
О мультираскраске инциденторов взвешенного ориентированного мультиграфа

Аннотация:
Рассматриваются ориентированные мультиграфы с взвешенными дугами. При мультираскраске инциденторов каждому инцидентору сопоставляется мультицвет, т. е. интервал цветов, длина которого равна весу инцидентора. Мультираскраска допустима, если мультицвета смежных инциденторов не пересекаются и для каждой дуги левый конец мультицвета начального инцидентора не больше левого конца мультицвета конечного инцидентора. Приводятся нижняя и верхняя оценки минимального числа цветов, необходимого для допустимой мультираскраски всех инциденторов мультиграфа.
Ил. 1, библиогр. 5.

Ключевые слова: инцидентор, мультираскраска, инциденторное мультихроматическое число.

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

Статья поступила 21 января 2014 г.
Исправленный вариант — 11 марта 2014 г.

Литература

[1] Визинг В. Г. Об оценках инциденторного хроматического числа взвешенного ориентированного мультиграфа // Дискрет. анализ и исслед. операций. Сер. 1. - 2006. - Т. 13, №4. - С. 18–25.

[2] Визинг В. Г. О мультираскраске инциденторов взвешенного неориентированного мультиграфа // Дискрет. анализ и исслед. операций. - 2012. - Т. 19, №4. - С. 35–47.
Vizing V. G. Multicoloring the incidentors of a weighted undirected multigraph // J. Appl. Industr. Math. - 2012. - Vol. 6, N4. - P. 514–521.

[3] Визинг В. Г., Пяткин А. В. О раскраске инциденторов в ориентированном взвешенном мультиграфе // Дискрет. анализ и исслед. операций. Сер. 1. - 2006. - Т. 13, №1. - С. 33–44.

[4] Зыков А. А. Основы теории графов. - М: Вузовская книга, 2004. - 663 с.

[5] Пяткин А. В. Некоторые задачи оптимизации расписания передачи сообщений в локальной сети связи // Дискрет. анализ и исслед. операций. - 1995. - Т. 2, №4. - С. 74–79.