Toroidal graf

En toroidal graf  er en graf , der kan tegnes på en torus på en sådan måde, at dens kanter kun skærer hinanden ved fælles hjørner.

Formelt set er dette en graf, der kan indlejres i en torus .

Egenskaber

• Det kromatiske tal for enhver toroidal graf overstiger ikke 7 [1] .
  • Et eksempel på en toroidal graf med kromatisk nummer 7 er en komplet graf [2] .

• Det kromatiske tal for enhver toroidal graf uden trekanter overstiger ikke 4 [3] .

• Analogt med Farey-sætningen kan enhver toroidal graf tegnes med kanter som segmenter i et rektangel med periodiske grænser (det vil sige, at modsatte grænser af kvadratet er identificeret) [4] . Også Tuttas sætning gælder i dette tilfælde .

• Toroidale grafer tillader bogindlejring med maksimalt 7 ark [5] .

• Robertson-Seymour-sætningen garanterer, at toroidale grafer kan defineres af et begrænset sæt af forbudte grafer. Sættet af forbudte grafer i dette tilfælde er dog ukendt, og deres antal er mindst 250815 [6] .

Eksempler

• Enhver graf med skæringsnummer lig med 1 er toroidformet.
  • Det er især den komplette graf og den komplette todelte graf (" grafen for huse og brønde ") og alle andre Möbius-stiger .
• komplet graf ,
• komplet todelt graf ,
• greve af Petersen ,
• jarl af Heawood ,
• Möbius-Cantor graf [7] ,
• en af ​​Blanuchis snert [8] .

Se også

• Plan graf
• Topologisk grafteori
• Chasar polyeder

Noter

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

Links

• Chartrand, Gary; Zhang Ping. Kromatisk grafteori. - CRC Press, 2008. - ISBN 978-1-58488-800-0 .
• Endo, Toshiki. Sidetallet for toroidale grafer er højst syv // Diskret matematik. - 1997. - Vol. 175, nr. 1-3. - S. 87-96. - doi : 10.1016/S0012-365X(96)00144-6 .
• Gortler, Steven J.; Gotsman, Craig; Thurston, Dylan. Diskrete one-forms på masker og applikationer til 3D mesh-parameterisering // Computer Aided Geometric Design. - 2006. - Bd. 23, nr. 2. - S. 83-112. - doi : 10.1016/j.cagd.2005.05.002 .
• Heawood P. J. Kortfarvesætninger  // Quarterly J. Math. Oxford Ser. - 1890. - Vol. 24. - S. 322-339.
• Kocay W., Neilson D., Szypowski R.  Tegning af grafer på torus  // Ars Combinatoria. - 2001. - Bd. 59. - S. 259-277. Arkiveret fra originalen den 24. december 2004.
• Kronk, Hudson V.; White, Arthur T.  En 4-farvesætning for toroidale grafer // Proceedings of the American Mathematical Society . - 1972. - Bd. 34, nr. 1. - S. 83-86. - doi : 10.2307/2037902 .
• Marusic, Dragan; Pisanski, Tomaz.  Den bemærkelsesværdige generaliserede Petersen-graf G (8,3)  // Math. Slovaca. - 2000. - Vol. 50. - S. 117-121.  (utilgængeligt link)
• Myrvold, Wendy; Woodcock, Jennifer. Et stort sæt torus-forhindringer og hvordan de blev opdaget. - 2018. - Bd. 25. doi : 10.37236/3797 .
• Neufeld, Eugene; Myrvold, Wendy. Praktisk toroidalitetstest // Proceedings of the Eightth Annual ACM-SIAM Symposium on Discrete Algorithms. - 1997. - S. 574-580.
• Orbanic, Alen; Pisanski, Tomaz; Randic, Milano; Servatius, Brigitte. Blanuša dobbelt // Matematik. commun. - 2004. - Bd. 9, nr. 1. - S. 91-103.