EN|RU

Том 19, номер 4, 2012 г., Стр. 35-47

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

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

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

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

Статья поступила 18 ноября 2011 г.
Исправленный вариант — 26 января 2012г.

 © Институт математики им. С. Л. Соболева, 2015