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

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

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

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

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

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

Литература

[1] Аксёнов В. А. Степень совершенства графа // Методы дискретного анализа в изучении реализации логических функций. Сб. тр. Ин-та математики СО АН СССР. — 1984. — Вып. 41. — С. 3–11.

[2] Аксёнов В. А. Обобщение некоторых оценок хроматического числа графов // 30th Int. Wiss. Koll. TH. — Ilmenau: Vortragsreihe, 1985. — С. 3–5.

[3] Аксёнов В. А. Полиномиальный алгоритм для приближённого решения одной задачи теории расписаний // 33th Int. Wiss. Koll. TH. — Ilmenau: Vortragsreihe, 1988. — С. 143–145.

[4] Визинг В. Г. О мультираскраске вершин взвешенных графов // Дискрет. анализ и исслед. операций. — 2007. — Т. 14, № 4. — С. 16–26.

[5] Визинг В. Г. Об одном обобщении задачи раскраски рёбер мультиграфа // Докл. Одесск. семинара по дискрет. математике. — 2007. — № 5. — С. 4–6.

[6] Визинг В. Г., Пяткин А. В. Об оценках инциденторного хроматического числа взвешенного неориентированного мультиграфа //Дискрет. анализ и исслед. операций. — 2007. — Т. 14, № 2. — С. 3–15.

[7] Визинг В. Г., Тофт Б. Раскраска инциденторов и вершин неориентированного мультиграфа // Дискрет. анализ и исслед. операций. Сер. 1. — 2001. — Т. 8, № 3. — С. 3–14.

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

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

[10] Golumbic M. C. Algorithmic graph theory and perfect graphs. — New York; London: Acad. Press, 1980. — 303 c.