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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Кубический граф с 14 вершинами, вложенный в тор

Тороида́льный граф — граф, который можно нарисовать на торе так, что его рёбра пересекались только по общим вершинам.

Формально говоря, это граф который допускает вложение в тор.

Свойства[править | править код]

  • По аналогии с теоремой Фари, любой тороидальный граф можно нарисовать с рёбрами в виде отрезков в прямоугольнике с периодическими границами (то есть противоположные границы квадрата отождествляются)[4]. Кроме того, в этом случае применима теорема Татта.
  • Теорема Робертсона — Сеймура гарантирует, что тороидальные графы можно определить конечным набором запрещённых графов. Однако набор запрещённых графов в этом случае неизвестен, и их число не менее 250815. [6]

Примеры[править | править код]

См. также[править | править код]

Примечания[править | править код]

  1. Heawood, 1890.
  2. Chartrand & Zhang, 2008.
  3. Kronk & White, 1972.
  4. Kocay, Neilson, Szypowski, 2001.
  5. Endo, 1997.
  6. Myrvold, Wendy; Woodcock, Jennifer (2018), "A large set of torus obstructions and how they were discovered", Electronic Journal of Combinatorics, 25 (1): P1.16
  7. Marušič & Pisanski, 2000.
  8. Orbanić et al., 2004.

Ссылки[править | править код]

  • 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:10.1016/S0012-365X(96)00144-6.
  • 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:10.1016/j.cagd.2005.05.002.
  • Heawood P. J.  Map colouring theorems // Quarterly J. Math. Oxford Ser.. — 1890. — Vol. 24. — P. 322—339.
  • Kocay W., Neilson D., Szypowski R.  Drawing graphs on the torus // 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:10.2307/2037902.
  • Marušič, Dragan; Pisanski, Tomaž.  The remarkable generalized Petersen graph G(8,3) // Math. Slovaca. — 2000. — Vol. 50. — P. 117—121. (недоступная ссылка)
  • Neufeld, Eugene; Myrvold, Wendy. . Practical toroidality testing // 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.