Эффективная разрешимость задачи о взвешенной вершинной раскраске для некоторых двух наследственных классов графов

Задача о взвешенной вершинной раскраске для заданного взвешенного графа состоит в том, чтобы минимизировать количество используемых цветов так, что для каждой вершины количество назначаемых ей цветов равно её весу и назначаемые множества цветов для любых смежных вершин не пересекаются. Для всех наследственных классов, определяемых двумя связными 5-вершинными порождёнными запретами, кроме четырёх случаев, известна вычислительная сложность варианта задачи о взвешенной вершинной раскраске с единичными весами. Для четырёх из шести попарных пересечений данных четырёх классов ранее была доказана разрешимость задачи о взвешенной вершинной раскраске за полиномиальное от суммы весов вершин время. Для оставшихся двух таких пересечений данный факт устанавливается в настоящей работе. Библиогр. 17.