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

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

Граф Хивуда и связанная с ним карта, встроенная в тор.

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

Примеры

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

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

Характеристики

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

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

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

Препятствия

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

Галерея

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

См. также

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

Ссылки

• Шартран, Гэри ; Чжан, Пин (2008), Теория хроматических графов , CRC Press, ISBN  978-1-58488-800-0 .
• Эндо, Тошики (1997), «Количество страниц тороидальных графов не превышает семи», Discrete Mathematics , 175 (1–3): 87–96, doi : 10.1016/S0012-365X(96)00144-6 , MR   1475841 .
• Гортлер, Стивен Дж.; Гоцман, Крейг; Терстон, Дилан (2006), «Дискретные формы на сетках и приложения к параметризации трехмерных сеток» (PDF) , Компьютерное геометрическое проектирование , 23 (2): 83–112, doi : 10.1016/j.cagd.2005.05.002 , МР   2189438 , S2CID   135438 .
• Хивуд, П.Дж. (1890), «Теоремы о раскраске карт», Ежеквартальный журнал математики , первая серия, 24 : 322–339 .
• Кочай, В.; Нилсон, Д.; Шиповски, Р. (2001), «Рисование графов на торе» (PDF) , Ars Combinatoria , 59 : 259–277, MR   1832459 , заархивировано из оригинала (PDF) 24 декабря 2004 г. , получено 9 сентября 2018 г. 06 .
• Кронк, Хадсон В.; Уайт, Артур Т. (1972), «Теорема о 4 цветах для тороидальных графов», Proceedings of the American Mathematical Society , 34 (1), American Mathematical Society: 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 .
• Мирволд, Венди ; Вудкок, Дженнифер (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 .