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