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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Кубічний граф з 14 вершинами, вкладений в тор

Тороїдальний граф — це граф, який можна вкласти на тор; іншими словами, це — граф, вершини якого можна розмістити на торі так, що ребра не схрещуватимуться.

Приклади

[ред. | ред. код]

Будь-який граф, який можна вкласти у площину, також можна вкласти у тор. Тороїдальний будь-який граф із числом схрещень 1, наприклад: граф Хівуда, повний граф (і як наслідок, та ), граф Петерсена, один зі снарків Блануші[1] та всі драбини Мебіуса. Деякі графи з великим числом схрещень також є тороїдальними, наприклад, граф Мебіуса — Кантора, який має число схрещень 4[2].

Властивості

[ред. | ред. код]

Хроматичне число будь-якого тороїдального графа не перевищує 7[3]; прикладом тороїдального графа з хроматичним числом 7 є повний граф [4]. Хроматичне число будь-якого тороїдального графа без трикутників не перевищує 4[5].

Аналогічно теоремі Фарі, будь-який тороїдальний граф можна побудувати з ребрами у вигляді відрізків у прямокутнику з періодичними межами (тобто протилежні границі квадрата ототожнюються)[6]. Крім того, у цьому випадку може бути застосована теорема Татта[7].

Тороїдальні графи також допускають книжкове вкладення з максимум 7 листами[8].

Див. також

[ред. | ред. код]

Примітки

[ред. | ред. код]

Література

[ред. | ред. код]
  • Chartrand, Gary; Zhang, Ping (2008), Chromatic graph theory, CRC Press, ISBN 978-1-58488-800-0.
  • Endo, Toshiki (1997), The pagenumber of toroidal graphs is at most seven, Discrete Mathematics, 175 (1–3): 87—96, doi:10.1016/S0012-365X(96)00144-6, MR 1475841.
  • Gortler, Steven J.; Gotsman, Craig; Thurston, Dylan (2006), Discrete one-forms on meshes and applications to 3D mesh parameterization, Computer Aided Geometric Design, 23 (2): 83—112, doi:10.1016/j.cagd.2005.05.002, MR 2189438.
  • Heawood, P. J. (1890), Map colouring theorems, Quarterly J. Math. Oxford Ser., 24: 322—339.
  • Kocay, W.; Neilson, D.; Szypowski, R. (2001), Drawing graphs on the torus (PDF), Ars Combinatoria, 59: 259—277, MR 1832459, архів оригіналу (PDF) за 24 грудня 2004, процитовано 9 травня 2019.
  • Kronk, Hudson V.; White, Arthur T. (1972), A 4-color theorem for toroidal graphs, Proceedings of the American Mathematical Society, American Mathematical Society, 34 (1): 83—86, doi:10.2307/2037902, JSTOR 2037902, MR 0291019.
  • Marušič, Dragan; Pisanski, Tomaž (2000), The remarkable generalized Petersen graph G(8,3), Math. Slovaca, 50: 117—121[недоступне посилання з травня 2019].
  • Neufeld, Eugene; Myrvold, Wendy (1997), Practical toroidality testing, Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, с. 574—580.
  • Orbanić, Alen; Pisanski, Tomaž; Randić, Milan; Servatius, Brigitte (2004), Blanuša double, Math. Commun., 9 (1): 91—103.