Граф Голомба

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

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

Построение

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

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

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

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

Литература

1. Alexander Soifer. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators. — New York: Springer, 2008. — С. 19. — ISBN 978-0-387-74640-1.
2. Arjana Žitnik, Boris Horvat, Tomaž Pisanski. All generalized Petersen graphs are unit-distance graphs // Journal of the Korean Mathematical Society. — 2012. — Т. 49, вып. 3. — С. 475–491. — doi:10.4134/JKMS.2012.49.3.475.
3. Ed Pegg, Jr. Moser Spindles, Golomb Graphs and Root 33 // Wolfram Demonstrations Project. — 2017. — Декабрь. Архивировано 28 января 2019 года.
4. Daniel W. Cranston, Landon Rabern. The fractional chromatic number of the plane // Combinatorica. — 2017. — Т. 37, вып. 5. — С. 837–861. — doi:10.1007/s00493-016-3380-3. — arXiv:1501.01647.

Ссылки

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