В теории графов граф Голомба представляет собой многогранный граф с 10 вершинами и 18 ребрами . Он назван в честь Соломона В. Голомба , который построил его (с неплоским вложением ) как граф единичных расстояний , требующий четырех цветов в любой раскраске графа . Таким образом, как и более простое веретено Мозера , оно обеспечивает нижнюю оценку проблемы Хадвигера-Нельсона : для раскраски точек евклидовой плоскости так, чтобы каждый сегмент единичной прямой имел конечные точки разного цвета, требуется как минимум четыре цвета. [1]
Метод построения графа Голомба как графа единичных расстояний путем рисования внешнего правильного многоугольника, соединенного с внутренним скрученным многоугольником или звездчатым многоугольником, также использовался для представлений на единичном расстоянии графа Петерсена и обобщенных графов Петерсена . [2] Как и в случае с веретеном Мозера, координаты вложения графа Голомба на единичное расстояние могут быть представлены в квадратичном поле . [3]
Дробное хроматическое число графа Голомба равно 10/3. Тот факт, что это число как минимум столь велико, следует из того, что граф имеет 10 вершин, не более трех из которых могут находиться в любом независимом множестве. Тот факт, что это число не превышает такого большого значения, следует из того факта, что можно найти 10 независимых трехвершинных множеств, таких, что каждая вершина находится ровно в трех из этих множеств. Это дробное хроматическое число меньше числа 7/2 для веретена Мозера и меньше дробного хроматического числа графа единичных расстояний на плоскости, которое ограничено значениями от 3,6190 до 4,3599. [4]
![{\displaystyle \mathbb {Q} [{\sqrt {33}}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b920b3da2daef8f7f2ff1cbc6618b2ad08963bd)