Эффективная разрешимость задачи о взвешенной вершинной раскраске для некоторого наследственного класса графов с $5$-вершинными запретами

Рассматривается задача минимизации количества цветов в раскрасках вершин задаваемого графа так, что каждой вершине назначаются цвета, число которых равно задаваемому весу вершины, причём смежным вершинам назначаются различные цвета. Для всех наследственных классов, определяемых парой связных $5$-вершинных порождённых запретов, кроме четырёх случаев, известна вычислительная сложность варианта задачи о взвешенной вершинной раскраске с единичными весами. В настоящей работе доказывается полиномиальная разрешимость от суммы весов вершин для данной задачи и пересечения двух из четырёх открытых случаев. Авторы надеются, что этот результат будет способствовать прояснению вычислительного статуса задачи о вершинной раскраске в упомянутых открытых случаях. Ил. 1, библиогр. 18.