Том 2, номер 4, 1995 г., Стр. 3-12
УДК 519.1
В. Г. Визинг
Дистрибутивная раскраска вершин графа
Аннотация:
Два вершинных подмножества в графе с раскрашенными вершинами называются соцветными, если в этих подмножествах содержится по одинаковому числу вершин каждого цвета. Раскраска вершин графа называется дистрибутивной, если соцветны окружения любых вершин одного цвета. В статье изучаются свойства минимальных дистрибутивных раскрасок и излагается алгоритм полиномиальной сложности, позволяющий находить такие раскраски.
Ил. 2, библиогр. 2.
Визинг В. Г. 1
1. Одесская гос. академия пищевых технологий,
ул. Канатная, 112, 65070 Одесса, Украина
Статья поступила 6 июня 1995 г.
