Toroid gráf

A toroid gráf  olyan gráf , amely úgy rajzolható meg a tóruszra, hogy az élei csak közös csúcsokban metszik egymást.

Formálisan ez egy tóruszba ágyazható gráf .

Tulajdonságok

• Egyetlen toroid gráf kromatikus száma sem haladja meg a 7 -et [1] .
  • Példa a 7-es kromatikus számú toroid gráfra egy teljes gráf [2] .

• A háromszög nélküli toroid gráf kromatikus száma nem haladja meg a 4 -et [3] .

• A Farey-tételhez hasonlóan bármely toroid gráf megrajzolható élekkel, mint szegmensekkel egy periodikus határokkal rendelkező téglalapban (azaz a négyzet ellentétes határait azonosítjuk) [4] . Ebben az esetben is érvényes a Tutta-tétel .

• A toroid gráfok legfeljebb 7 lapos könyvek egymásba ágyazását teszik lehetővé [5] .

• A Robertson-Seymour tétel garantálja, hogy a toroid gráfok tiltott gráfok véges halmazával definiálhatók. A tiltott gráfok halmaza azonban ebben az esetben nem ismert, és számuk legalább 250815 [6] .

Példák

• Bármely gráf, amelynek metszéspontszáma 1, toroid alakú.
  • Különösen ilyen a teljes gráf és a teljes kétrészes gráf (" házak és kutak " gráf) és az összes többi Möbius-létra .
• teljes grafikon ,
• teljes kétrészes gráf ,
• Petersen grófja ,
• Heawood grófja ,
• Möbius-Cantor gráf [7] ,
• Blanuchi egyik snarkja [8] .

Lásd még

• Síkgrafikon
• Topológiai gráfelmélet
• Chasar poliéder

Jegyzetek

1. ↑ Heawood, 1890 .
2. ↑ Chartrand és Zhang, 2008 .
3. ↑ Kronk & White, 1972 .
4. ↑ Kocay, Neilson, Szypowski, 2001 .
5. ↑ Endo, 1997 .
6. ↑ Myrvold & Woodcock, 2018 .
7. ↑ Marusic & Pisanski, 2000 .
8. ↑ Orbánic et al., 2004 .

Linkek

• Chartrand, Gary; Zhang Ping. Kromatikus gráf elmélet. - CRC Press, 2008. - ISBN 978-1-58488-800-0 .
• Endo, Toshiki. A toroid gráfok oldalszáma legfeljebb hét // Discrete Mathematics. - 1997. - 1. évf. 175. sz. 1–3. - P. 87-96. - doi : 10.1016/S0012-365X(96)00144-6 .
• Gortler, Steven J.; Gotsman, Craig; Thurston, Dylan. Diszkrét egyformák hálókon és alkalmazásokon a 3D hálóparaméterezéshez // Számítógéppel segített geometriai tervezés. - 2006. - Vol. 23. sz. 2. - P. 83-112. - doi : 10.1016/j.cagd.2005.05.002 .
• Heawood P. J.  Térképszínezési tételek // Quarterly J. Math. Oxford Ser. – 1890. – 1. évf. 24. - P. 322-339.
• Kocay W., Neilson D., Szypowski R.  Grafikonok rajzolása a tóruszra  // Ars Combinatoria. - 2001. - 20. évf. 59. - P. 259-277. Az eredetiből archiválva : 2004. december 24.
• Kronk, Hudson V.; White, Arthur T.  Négyszínű tétel toroid gráfokhoz // Proceedings of the American Mathematical Society . - 1972. - 1. évf. 34, sz. 1. - P. 83-86. - doi : 10.2307/2037902 .
• Marusic, Dragan; Pisanski, Tomaz.  A figyelemre méltó általánosított Petersen-gráf G (8,3)  // Math. Szlovákia. - 2000. - Vol. 50. - P. 117-121.  (nem elérhető link)
• Myrvold, Wendy; Woodcock, Jennifer. Tórusz akadályok nagy halmaza és felfedezésük módja. - 2018. - Kt. 25. doi : 10.37236/3797 .
• Neufeld, Eugene; Myrvold, Wendy. Gyakorlati toroiditási tesztelés // Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. - 1997. - P. 574-580.
• Orbánic, Alen; Pisanski, Tomaz; Randic, Milánó; Servatius, Brigitte. Blanuša double // Math. kommun. - 2004. - 20. évf. 9, sz. 1. - P. 91-103.