Введение

Граф, который может быть изображён на торе. В математической области теории графов, тороидальный граф — это граф, который можно изобразить на торе. Иными словами, вершины и рёбра графа можно расположить на торе так, чтобы рёбра не пересекались, за исключением общих вершин.

Примеры

Любой граф, который может быть вложен в плоскость, также может быть вложен в тор, поэтому каждый планарный граф также является тороидальным графом. Тороидальный граф, который не может быть вложен в плоскость, называется графом рода 1. Граф Хьювуда, полный граф K7 (и, следовательно, K5 и K6), граф Петерсена (и, следовательно, полный двудольный граф K3,3, поскольку граф Петерсена содержит его подразделение), один из шнурков Блануши и все лестницы Мёбиуса являются тороидальными. В более общем смысле, любой граф с числом пересечений 1 является тороидальным. Некоторые графы с большим числом пересечений также являются тороидальными: например, граф Мёбиуса — Кантора имеет число пересечений 4 и является тороидальным.

Свойства

Любой тороидальный граф имеет хроматическое число не более 7. Полный граф K7 является примером тороидального графа с хроматическим числом 7. Любой тороидальный граф, не содержащий треугольников, имеет хроматическое число не более 4. По результату, аналогичному теореме Фари, любой тороидальный граф можно изобразить прямыми ребрами в прямоугольнике с периодическими граничными условиями. Кроме того, в этом случае применима аналогия теоремы о пружинах Тютте. Тороидальные графы также допускают книжные вложения не более чем на 7 страницах.

Препятствия

По теореме Робертсона — Сеймура существует конечное множество H минимальных нетороидных графов, таких что граф является тороидным тогда и только тогда, когда он не содержит ни одного графа из H в качестве минора. Иными словами, H образует множество запрещенных миноров для тороидных графов. Полный состав множества H неизвестен, но известно, что оно содержит не менее 17 523 графов. Альтернативно, существует не менее 250 815 нетороидных графов, минимальных в отношении топологического минора. Граф является тороидным тогда и только тогда, когда он не имеет ни одного из этих графов в качестве топологического минора.