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

Как упоминалось выше, использование векторной раскраски в контексте приближенной раскраски было впервые предложено в работе [15]. Грубо говоря, при наличии векторной раскраски графа G алгоритм, предложенный в [15], находит большое независимое множество в G. Это независимое множество соответствует множеству векторов в векторной раскраске, находящихся близко друг другу (и следовательно, по определению, не имеющих общей дуги). Сочетание этого подхода с идеями Вигдерсона [20] доказывает справедливость теоремы 1.