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

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

Кубічний граф з 14 вершинами, вкладений в тор

Приклади

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

Властивості

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

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

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

Див. також

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

Література

• 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.