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

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