График Голомба
-
Описание графа Голомба
- Многогранный граф с 10 вершинами и 18 ребрами
- Назван в честь Соломона У. Голомба
- Построен как граф единичных расстояний, требующий четырех цветов в раскраске
-
Применение в задаче Хадвигера-Нельсона
- Обеспечивает нижнюю границу для задачи Хадвигера-Нельсона
- Для раскрашивания точек евклидовой плоскости требуется минимум четыре цвета
-
Метод построения
- Построен путем соединения внешнего правильного многоугольника с внутренним скрученным многоугольником
- Использовался для представления графа Петерсена и обобщенных графов Петерсена
- Координаты вложения графа Голомба могут быть представлены в квадратичном поле Q[33]
-
Дробная окраска
- Дробное хроматическое число равно 10/3
- Число не более 10/3 следует из наличия 10 вершин и не более трех независимых множеств
- Число меньше 7/2 для шпинделя Мозера и меньше дробного хроматического числа для графика единичных расстояний на плоскости