Аннотация. Используются сведения, вводящие и сохраняющие разрыв. Показано, что для множественной реоптимизации задачи о вычислении хроматического числа графа с заданным экспоненциальным множеством оптимальных решений при вставке произвольной вершины с не более чем двумя ребрами, ей инцидентными, а также при удалении произвольной вершины со всеми инцидентными ей ребрами не существует полиномиально приближенной схемы (PTAS). Такой же результат имеет место для обычной реоптимизации.

Ключевые слова: множественная реоптимизация, сведения задач, вводящих и сохраняющих разрыв, APX-трудность, полиномиально приближенные схемы (PTAS).