Тороида́льный граф — граф, который можно нарисовать на торе так, что его рёбра пересекаются только по общим вершинам.
Формально говоря, это граф который допускает вложение в тор.
Свойства Хроматическое число любого тороидального графа не превышает 7. Пример тороидального графа с хроматическим числом 7 — полный граф .
Хроматическое число любого тороидального графа без треугольников не превосходит 4.
По аналогии с теоремой Фари, любой тороидальный граф можно нарисовать с рёбрами в виде отрезков в прямоугольнике с периодическими границами (то есть противоположные границы квадрата отождествляются). Кроме того, в этом случае применима теорема Татта.
Тороидальные графы допускают книжное вложение с максимум 7 листами.
Теорема Робертсона — Сеймура гарантирует, что тороидальные графы можно определить конечным набором запрещённых графов. Однако набор запрещённых графов в этом случае неизвестен, и их число не менее 250815.
Примеры Любой граф с числом пересечений равным 1 тороидален. В частности, таковы полный граф и полный двудольный граф (граф «домики и колодцы») и все остальные лестницы Мёбиуса. полный граф , полный двудольный граф , граф Петерсена, граф Хивуда, граф Мёбиуса — Кантора, один из снарков Блануши.
См. также Планарный граф Топологическая теория графов Многогранник Часара
Примечания
Ссылки
Категория:Семейства графов Категория:Топологическая теория графов