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

Векторные раскраски, включая <math>\theta</math>-функцию Ловаса и ее варианты, также активно изучались в контексте алгоритмов аппроксимации и для других задач – таких как аппроксимация <math>\alpha (G) \; </math>, аппроксимация задачи минимального вершинного покрытия и комбинаторная оптимизация в контексте случайных графов.