Справочный запрос: Асимптотическая твердость

10

Я слышал о результате в приблизительной окраске графика, но не могу найти источник. Результат:

Для каждой константы существует достаточно большое k, такое, что раскраска k- раскрашиваемого графа в h k цветов NP-трудна.hkkhk

Может ли кто-нибудь указать мне соответствующую статью?

Джереми Кун
источник

Ответы:

11

Существуют гораздо более сильные результаты для приблизительной раскраски графа.

Игорь Шинкарь
источник
Последний результат интересен, но есть ли там ошибка с десятичной точкой? Два нуля до запятой странно ...
Джереми Кун