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

Наконец, рассмотрим ограничения векторной раскраски. В частности, существуют ли графы, в которых <math>\overrightarrow{\chi} (G) \; </math> является грубой оценкой <math>\chi (G) \; </math>? Можно ожидать, что ответ будет положительным, поскольку оценка <math>\chi (G) \; </math> за пределами коэффициента <math>n^{1 - \varepsilon} \; </math> является сложной задачей. Так оно и оказывается на деле (даже если <math>\overrightarrow{\chi} (G) \; </math> мало). Некоторые из полученных результатов выражены в терминах максимального независимого множества <math>\alpha (G) \; </math> графа G. Поскольку <math>\chi (G) \ge n / \alpha (G) \; </math>, эти результаты налагают нижнюю границу на <math>\chi (G) \; </math>. Теорема 1 (i) утверждает, что выполненный в [15] изначальный анализ является строгим. Теорема 1 (ii) приводит границы для случая <math>\overrightarrow{\chi} (G) = 3 \; </math>. Пункт (iii) теоремы 1 и теорема 2 представляют графы, в которых имеется исключительно большой разрыв между <math>\chi (G) \; </math> и релаксациями <math>\overrightarrow{\chi} (G) \; </math> и <math>\overrightarrow{\chi}_2 (G) \; </math>.