4446
правок
Раскраска графа: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Векторная раскраска графов
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 56: | Строка 56: | ||
<math>\langle v_i, v_j \rangle \ge - \frac {1} {k - 1} \; \; \forall i, j \in V</math> | <math>\langle v_i, v_j \rangle \ge - \frac {1} {k - 1} \; \; \forall i, j \in V</math> | ||
<math>\langle v_i, | <math>\langle v_i, v_i \rangle = 1 \; \; \forall i \in V</math>. | ||
Функция | Функция <math>\overrightarrow{\chi}_2 (G)</math>, вычисляющая '''точное''' векторное хроматическое число графа G, равна <math>\theta</math>-функции Ловаса на <math>\bar{G}</math> [15, 19], где <math>\bar{G}</math> – дополнение графа G. Функция <math>\overrightarrow{\chi}_3 (G)</math> называется '''сильным''' векторным хроматическим числом. Аналог утверждения 1 верен как для <math>\overrightarrow{\chi}_2 (G)</math>, так и для <math>\overrightarrow{\chi}_3 (G)</math>. Обозначим размер максимальной клики графа G как <math>\omega (G) \; </math>; тогда имеет место соотношение <math>\omega(G) \le \overrightarrow{\chi} (G) \le \overrightarrow{\chi}_2 (G) \le \overrightarrow{\chi}_3 (G) \le \chi (G) \; </math>. | ||
== Основные результаты == | == Основные результаты == | ||