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

'''Теорема 7 ([10]) (i). Для всех константных значений <math>\varepsilon > 0 \; </math> и <math>k > 2 \; </math> существует бесконечное число графов <math>G \; </math>, таких, что <math>\overrightarrow{\chi} (G) = k \; </math> и <math>\alpha (G) \le n / \Delta^{1-2/k - \varepsilon}</math> (здесь <math>\Delta > n^{\delta} \; </math> для некоторой константы <math>\delta > 0 \; </math>). (ii) Существует бесконечное число графов <math>G \; </math>, таких, что <math>\overrightarrow{\chi} (G) = 3 \; </math> и <math>\alpha (G) \le n^{0.843} \; </math>. (iii) Для некоторого константного значения <math>c \; </math> существует бесконечное число графов <math>G \; </math>, таких, что <math>\overrightarrow{\chi} (G) = O(log \; n/log \; log \; n) \; </math> и <math>\alpha (G) \le log^c n \; </math>.'''

'''Теорема 8 ([7]). Для некоторого константного значения <math>c \; </math> существует бесконечное число графов <math>G \; </math>, таких, что <math>\overrightarrow{\chi}_2 (G) \le 2 \sqrt{log \; n} \; </math> и <math>\chi (G) \ge n / 2^{c \sqrt{log \; n}} \; </math>  >'''

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