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

12

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

( имеет векторное хроматическое число если существует присваивание , где векторы, связанные с соседними вершинами, интуитивно находятся далеко друг от друга. Требование . Например, для вершин треугольника.)Gqx:VRdx(v),x(w)1/(q1)q=3

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

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

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

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

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

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

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

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

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

Тор Хусфельдт
источник
1
Не могли бы вы предоставить ссылку или определение для векторного хроматического числа?
Суреш Венкат
4
χv(C5)=5<3=χ(C5) , где - цикл из 5 вершин. - наименьший граф st . C5C5Gχv(G)χ(G)
Юрий

Ответы:

7

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

χv(C5)=5<3=χ(C5).[Lovász]

Нетрудно преобразовать этот пример в пример, где - целое число. Пусть является объединением двух 5-циклов и в которых каждая вершина из соединена с каждой вершиной в , Пусть . Наконец, пусть будет объединением и . Тогда χv(G)G1C5(1)C5(2)C5(1)C5(2)G2=K5GG1G2

χ(G)=max(χ(G1),χ(G2))=χ(G1)=6.χv(G)=max(χv(G1),χv(G2))=max(25,5)=5.
Юрий
источник
3

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

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

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

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

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

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

Тор Хусфельдт
источник