Граф Голомба

Граф Голомба
Назван в честь	Соломона Вольфа Голомба
Вершин	10
Рёбер	18
Хроматическое число	4
Свойства	Полиэдральный Граф единичных расстояний
Медиафайлы на Викискладе

Граф Голомба — полиэдральный граф с 10 вершинами и 18 рёбрами. Граф назван именем Соломона Вольфа Голомба, который построил его (с непланарным вложением) как граф единичных расстояний, который требует четыре цвета для раскраски. Таким образом, подобно более простому веретену Мозера, граф даёт нижнюю границу для задачи Нелсона — Эрдёша — Хадвигера — раскраска точек евклидовой плоскости, так что единичный отрезок имеет различные цвета на концах, требует по меньшей мере четырёх цветов.

Построение

4-цветная раскраска графа Голомба, нарисованного как граф единичных расстояний

Метод построения графа Голомба как графа единичных расстояний, заключающийся в рисовании внешнего правильного многоугольника, соединённого с внутренним повёрнутым многоугольником или звездой, используется также для представления графа Петерсена и обобщённых графов Петерсена. Как и в случае веретена Мозера, координаты вложения графа Голомба с единичными расстояниями может быть представлены в квадратичном поле $\mathbb {Q} [{\sqrt {33}}]$.

Дробная раскраска

Дробное хроматическое число графа Голомба равно 10/3. Факт, что это число не меньше указанного значения, следует из того, что граф имеет 10 вершин и максимум три из них могут быть в каком-либо независимом множестве. Факт, что это значение не превосходит этой величины, следует из того, что можно найти 10 независимых множеств из трёх вершин, таких, что каждая вершина находится ровно в трёх таких множествах. Это дробное хроматическое число меньше, чем 7/2 у веретена Мозера и меньше, чем дробное хроматическое число графа единичных расстояний плоскости, которое лежит между 3,6190 и 4,3599.

Ссылки

• Weisstein, Eric W. Golomb Graph (англ.) на сайте Wolfram MathWorld.