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

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

Любой граф, который может быть вложен в плоскость, может быть вложен и в тор, поэтому каждый планарный граф также является тороидальным графом. Говорят, что тороидальный граф, который не может быть вложен в плоскость, имеет род 1.

Граф Хивуда , полный граф K ₇ (и, следовательно, K ₅ и K ₆ ), граф Петерсена (и, следовательно, полный двудольный граф K _3,3 , поскольку граф Петерсена содержит его подразделение), один из снарков Блануши ^[1] и все лестницы Мёбиуса являются тороидальными. В более общем смысле, любой граф с числом пересечений 1 является тороидальным. Некоторые графы с большим числом пересечений также являются тороидальными: например, граф Мёбиуса–Кантора имеет число пересечений 4 и является тороидальным. ^[2]

Любой тороидальный граф имеет хроматическое число не более 7. ^[3] Полный граф K ₇ представляет собой пример тороидального графа с хроматическим числом 7. ^[4]

Любой тороидальный граф без треугольников имеет хроматическое число не более 4. ^[5]

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

По теореме Робертсона–Сеймура существует конечное множество H минимальных нетороидальных графов, такое, что граф является тороидальным тогда и только тогда, когда он не имеет минора графа в H. То есть, H образует множество запрещенных миноров для тороидальных графов. Полное множество H неизвестно, но оно содержит не менее 17 523 графов. В качестве альтернативы, существует не менее 250 815 нетороидальных графов, которые минимальны в топологическом минорном порядке. Граф является тороидальным тогда и только тогда, когда он не содержит ни одного из этих графов в качестве топологического минора. ^[9]

• 
  Два изоморфных графа Кэли группы кватернионов .
• 
  Граф Кэли группы кватернионов, вложенный в тор.
• Видео графа Кэли группы кватернионов, вложенной в тор.
• 
  Граф Паппуса и связанная с ним карта, встроенная в тор.

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

• Шартран, Гэри ; Чжан, Пин (2008), Хроматическая теория графов , CRC Press, ISBN 978-1-58488-800-0.
• Эндо, Тошики (1997), «Количество страниц тороидальных графов не превышает семи», Дискретная математика , 175 (1–3): 87–96, doi :10.1016/S0012-365X(96)00144-6, MR  1475841.
• Гортлер, Стивен Дж.; Готсман, Крейг; Терстон, Дилан (2006), «Дискретные формы на сетках и приложения к параметризации трехмерных сеток» (PDF) , Computer Aided Geometric Design , 23 (2): 83–112, doi :10.1016/j.cagd.2005.05.002, MR  2189438, S2CID  135438.
• Хивуд, П. Дж. (1890), «Теорема о цвете карты», Quarterly Journal of Pure and Applied Mathematics , First Series, 24 : 322–339.
• Kocay, W.; Neilson, D.; Szypowski, R. (2001), "Рисование графов на торе" (PDF) , Ars Combinatoria , 59 : 259–277, MR  1832459, архивировано из оригинала (PDF) 24.12.2004 , извлечено 06.09.2018.
• Кронк, Хадсон В.; Уайт, Артур Т. (1972), «Теорема о 4 цветах для тороидальных графов», Труды Американского математического общества , 34 (1), Американское математическое общество: 83–86, doi :10.2307/2037902, JSTOR  2037902, MR  0291019.
• Марушич, Драган ; Писански, Томаж (2000), «Замечательный обобщенный граф Петерсена G (8,3)», Math. Словака , 50 : 117–121, CiteSeerX  10.1.1.28.7183 , hdl :10338.dmlcz/133137, MR  1763113, Zbl  0984.05044.
• Myrvold, Wendy ; Woodcock, Jennifer (2018), «Большой набор препятствий тора и как они были обнаружены», Electronic Journal of Combinatorics , 25 (1): P1.16, doi : 10.37236/3797
• Нойфельд, Юджин; Мирвольд, Венди (1997), «Практическое тестирование тороидальности», Труды восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , стр. 574–580, ISBN 978-0-89871-390-9.
• Орбанич, Ален; Писански, Томаж ; Рандич, Милан ; Серватиус, Бриджит (2004), «Двойник Блануши» (PDF) , Math. Коммун. , 9 (1): 91–103, CiteSeerX  10.1.1.361.2772.