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