Небольшой график с разрывом между хроматическим и векторным хроматическим числом?

Я ищу небольшой граф которого векторное хроматическое число меньше хроматического числа, .$G$$\chi_v(G)<\chi(G)$

( имеет векторное хроматическое число если существует присваивание , где векторы, связанные с соседними вершинами, интуитивно находятся далеко друг от друга. Требование . Например, для вершин треугольника.)$G$$q$$x\colon V \rightarrow \mathbf R^d$$\langle x(v), x(w)\rangle \leq -1/(q-1)$$q=3$

Хроматическое число вектора графа не больше хроматического числа: . Известны примеры графов с . (Оригинальная статья Каргера, Мотвани, Судан [JACM, 45: 246-265] ( рукопись ) предлагает обобщенные графы Кнезера, более поздняя статья использует конструкцию, основанную на случайных единичных векторах.)$\chi_v(G)\leq \chi(G)$$\chi_v(G)=3$ $\chi(G)=n^\delta$

Я думаю, что у меня есть пример графа с и (на основе компьютерных расчетов). Этот граф имеет 20 вершин и 90 ребер.χ v ( K ) = 4 χ ( K ) = $K$$\chi_v(K)=4$$\chi(K)=8$

Есть ли маленький пример? Заманчивым подходом было бы обеспечить конкретную векторную 3-раскраску графа Хватала или Грёша, если такой зверь существует.

( не должен быть целым числом, но было бы неплохо. Обновление: как указано ниже, неинтегральный случай действительно прост. Спасибо.)$\chi_v$

Обновление: Grötzsch и Chvátal

Я не мог удержаться от размышлений о векторной 3-раскраске графиков Хватала и Грёша.

Граф Грёша может быть векторным 3-цветным, как показано ниже: Поместите узел степени пять на Северный полюс. Узлы 5 градусов-4 равномерно расположены на одной широте, примерно в 77 градусах от севера: представьте пентраграмму, нарисованную на северном полушарии Земли. Оставшиеся 5 узлов (степени 3) оказываются в южном полушарии, примерно в 135 градусах от севера. Имеют ту же долготу, что и 5 других. (Я загружу чертеж, когда он у меня будет, но в TikZ рисовать геодезические линии сложнее, чем я думал.)

Согласно решателю SDP, Chvátal также допускает векторную 3-раскраску, но на выходе получается просто набор векторов в 5 измерениях, которые мне трудно интерпретировать.

(Третья попытка не удалась: вдохновленный конструкцией Юрия, возьмите 5-цикл и добавьте вершину вершины, смежную со всеми остальными. Этот граф имеет хроматическое число 4. Но, согласно моему решателю, он не является векторным 3-цветным.)

Я делаю свой комментарий ответом. Если нам не требуется, чтобы было целым числом, то наименьшим примером является (цикл из 5 вершин): $\chi_v(G)$$G=C_5$

$$\chi_v(C_5) = \sqrt{5} < 3 = \chi(C_5) . \qquad\text{[Lovász]}$$

Нетрудно преобразовать этот пример в пример, где - целое число. Пусть является объединением двух 5-циклов и в которых каждая вершина из соединена с каждой вершиной в , Пусть . Наконец, пусть будет объединением и . Тогда $\chi_v(G)$$G_1$$C_5^{(1)}$$C_5^{(2)}$$C_5^{(1)}$$C_5^{(2)}$$G_2=K_5$$G$$G_1$$G_2$

$$\begin{align*} \chi(G) &= \max(\chi(G_1), \chi(G_2)) = \chi(G_1) = 6.\\ \chi_v(G) &= \max(\chi_v(G_1), \chi_v(G_2)) = \max(2\cdot \sqrt{5}, 5) = 5. \end{align*}$$

Здесь это вложение графа Грёша на единичную сферу: это соответствует векторной раскраске очевидным образом; например, вершина на северном полюсе окрашена вектором (0,0,1).

Граф Грёша имеет 3 типа узлов. Единый градус 5 узлов (на севере). Пять узлов степени 4 (в северном полушарии, равноудаленном от N, можно выделить 3 из них). Пять узлов степени 3 (в Южном полушарии, равноудаленных от N, можно выделить 3 из них).

N связан с его 5 соседями в южном полушарии с зелеными краями. (Обратите внимание, что зеленый край выглядит так, как будто он падает на вершины степени 4 в северном полушарии, но это артефакт вложения.)

При взгляде сверху вы можете разглядеть пентаграмму, описанную узлами степени 4, аналогично встраиванию в плоскость:$C_5$

Наконец, вид сверху на Южный полюс:

Если верить моим вычислениям, все соседние вершины находятся на расстоянии более 120 градусов друг от друга, так что это составляет действительную векторную 3-раскраску. Граф Грёша является 4-хроматическим. 11 вершин, 20 ребер. Я особенно рад этому примеру, потому что векторная раскраска в трех измерениях, вы можете визуализировать это. (И нарисуйте случайные гиперплоскости, чтобы объяснить алгоритм раскраски графов KMS.)