О мультираскраске вершин взвешенных графов

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