Том 14, серия 1, номер 4, 2007 г., Стр. 16-26

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

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

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

Статья поступила 22 июня 2007 г.
Исправленный вариант — 3 сентября 2007 г.