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

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

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

Приклади

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

Властивості

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

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

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

Див. також

Примітки
  1. Orbanić et al., 2004.
  2. Marušič & Pisanski, 2000.
  3. Heawood, 1890.
  4. Chartrand & Zhang, 2008.
  5. Kronk & White, 1972.
  6. Kocay, Neilson, Szypowski, 2001.
  7. Gortler, Gotsman, Thurston, 2006.
  8. Endo, 1997.

Література
  • 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. MR 1475841. doi:10.1016/S0012-365X(96)00144-6..
  • 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. MR 2189438. doi:10.1016/j.cagd.2005.05.002..
  • 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. Ars Combinatoria 59: 259–277. MR 1832459. Архів оригіналу за 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. JSTOR 2037902. MR 0291019. doi:10.2307/2037902..
  • 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..
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.