Раскраска графа: различия между версиями

Пусть G – граф размера n. Задача нахождения приближенной раскраски графа G может быть эффективно решена с коэффициентом аппроксимации r = O f"('°g'°g")2') [12]. Это верно также для аппроксимации <math>\alpha (G) \; </math> [8]. Эти результаты могут показаться довольно слабыми, однако задача аппроксимации <math>\alpha (G) \; </math> и <math>\chi (G) \; </math> с коэффициентом nl~e для любой константы " > 0 является NP-полной [9, 14, 21]. Если использовать более строгие соображения о сложности, существует константа 0 < 8 < 1, такая, что ни одна задача не может быть аппроксимирована с коэффициентом и/21о« " [17, 21]. Рассмотрим задачу раскраски графа G при малом значении <math>\chi (G) \; </math>. Как будет показано ниже, в данном случае достижимый коэффициент аппроксимации удается значительно улучшить.