Interested Article - Тороидальный граф
amity
- 2021-10-16
- 1
Тороида́льный граф — граф , который можно нарисовать на торе так, что его рёбра пересекаются только по общим вершинам.
Формально говоря, это граф который допускает вложение в тор .
Свойства
-
Хроматическое число
любого тороидального графа не превышает 7
.
- Пример тороидального графа с хроматическим числом 7 — полный граф .
- Хроматическое число любого тороидального графа без треугольников не превосходит 4 .
- По аналогии с теоремой Фари , любой тороидальный граф можно нарисовать с рёбрами в виде отрезков в прямоугольнике с периодическими границами (то есть противоположные границы квадрата отождествляются) . Кроме того, в этом случае применима теорема Татта .
- Тороидальные графы допускают книжное вложение с максимум 7 листами .
- Теорема Робертсона — Сеймура гарантирует, что тороидальные графы можно определить конечным набором запрещённых графов. Однако набор запрещённых графов в этом случае неизвестен, и их число не менее 250815 .
Примеры
-
Любой граф с
числом пересечений
равным 1 тороидален.
- В частности, таковы полный граф и полный двудольный граф (граф « домики и колодцы ») и все остальные лестницы Мёбиуса .
- полный граф ,
- полный двудольный граф ,
- граф Петерсена ,
- граф Хивуда ,
- граф Мёбиуса — Кантора ,
- один из снарков Блануши .
См. также
Примечания
- .
- .
- .
- .
- .
- .
- .
- .
Ссылки
- Chartrand, Gary; Zhang Ping. Chromatic graph theory. — CRC Press, 2008. — ISBN 978-1-58488-800-0 .
- Endo, Toshiki. The pagenumber of toroidal graphs is at most seven // Discrete Mathematics. — 1997. — Vol. 175, no. 1–3. — P. 87—96. — doi : .
- Gortler, Steven J.; Gotsman, Craig; Thurston, Dylan. Discrete one-forms on meshes and applications to 3D mesh parameterization // Computer Aided Geometric Design. — 2006. — Vol. 23, no. 2. — P. 83—112. — doi : .
- Heawood P. J. Map colouring theorems // Quarterly J. Math. Oxford Ser.. — 1890. — Vol. 24. — P. 322—339.
- Kocay W., Neilson D., Szypowski R. // Ars Combinatoria. — 2001. — Vol. 59. — P. 259—277. 24 декабря 2004 года.
- Kronk, Hudson V.; White, Arthur T. A 4-color theorem for toroidal graphs // Proceedings of the American Mathematical Society . — 1972. — Vol. 34, no. 1. — P. 83—86. — doi : .
- Marušič, Dragan; Pisanski, Tomaž. // Math. Slovaca. — 2000. — Vol. 50. — P. 117—121. (недоступная ссылка)
- Myrvold, Wendy; Woodcock, Jennifer. A large set of torus obstructions and how they were discovered. — 2018. — Vol. 25. — doi : .
- Neufeld, Eugene; Myrvold, Wendy . // Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. — 1997. — P. 574—580.
- Orbanić, Alen; Pisanski, Tomaž; Randić, Milan; Servatius, Brigitte. Blanuša double // Math. Commun. — 2004. — Vol. 9, no. 1. — P. 91—103.
amity
- 2021-10-16
- 1