Тороидальный граф

Тороида́льный граф — граф, который можно нарисовать на торе так, что его рёбра пересекаются только по общим вершинам.

Кубический граф с 14 вершинами, вложенный в тор

Формально говоря, это граф который допускает вложение в тор.

Свойства

• Хроматическое число любого тороидального графа не превышает 7^[1].
  • Пример тороидального графа с хроматическим числом 7 — полный граф ${\displaystyle K_{7}}$^[2].

• Хроматическое число любого тороидального графа без треугольников не превосходит 4^[3].

• По аналогии с теоремой Фари, любой тороидальный граф можно нарисовать с рёбрами в виде отрезков в прямоугольнике с периодическими границами (то есть противоположные границы квадрата отождествляются)^[4]. Кроме того, в этом случае применима теорема Татта.

• Тороидальные графы допускают книжное вложение с максимум 7 листами^[5].

• Теорема Робертсона — Сеймура гарантирует, что тороидальные графы можно определить конечным набором запрещённых графов. Однако набор запрещённых графов в этом случае неизвестен, и их число не менее 250815^[6].

Примеры

• Любой граф с числом пересечений равным 1 тороидален.
  • В частности, таковы полный граф ${\displaystyle K_{5}}$ и полный двудольный граф ${\displaystyle K_{3,3}}$ (граф «домики и колодцы») и все остальные лестницы Мёбиуса.
• полный граф ${\displaystyle K_{7}}$,
• полный двудольный граф ${\displaystyle K_{4,4}}$,
• граф Петерсена,
• граф Хивуда,
• граф Мёбиуса — Кантора^[7],
• один из снарков Блануши^[8].

См. также

• Планарный граф
• Топологическая теория графов
• Многогранник Часара