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

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

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

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

Свойства

• Хроматическое число любого тороидального графа не превышает 7Шаблон:Sfn.
  • Пример тороидального графа с хроматическим числом 7 — полный граф $K_7$Шаблон:Sfn.

• Хроматическое число любого тороидального графа без треугольников не превосходит 4Шаблон:Sfn.

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

• Тороидальные графы допускают книжное вложение с максимум 7 листамиШаблон:Sfn.

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

Примеры

• Любой граф с числом пересечений равным 1 тороидален.
  • В частности, таковы полный граф $K_5$ и полный двудольный граф $K_{3,3}$ (граф «домики и колодцы») и все остальные лестницы Мёбиуса.
• полный граф $K_7$,
• полный двудольный граф $K_{4,4}$,
• граф Петерсена,
• граф Хивуда,
• граф Мёбиуса — КантораШаблон:Sfn,
• один из снарков БланушиШаблон:Sfn.

См. также

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

Ссылки

• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:СтатьяШаблон:Недоступная ссылка
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья