Граф Голомба

8-06-2021, 09:00

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

Построение

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

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

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


  • Граф Фолкмана
  • Ядро (теория графов)
  • Граф Холта
  • Граф Дюрера
  • Гипотеза Шейнермана

  •  

    • Яндекс.Метрика
    • Индекс цитирования