Toroidal graf

En toroidgraf  är en graf som kan ritas på en torus på ett sådant sätt att dess kanter skär endast vid gemensamma hörn.

Formellt sett är detta en graf som kan bäddas in i en torus .

Egenskaper

• Det kromatiska talet för någon toroidal graf överstiger inte 7 [1] .
  • Ett exempel på en toroidal graf med kromatiskt nummer 7 är en komplett graf [2] .

• Det kromatiska talet för varje toroidal graf utan trianglar överstiger inte 4 [3] .

• I analogi med Farey-satsen kan vilken toroidform som helst ritas med kanter som segment i en rektangel med periodiska gränser (det vill säga att motsatta gränser av kvadraten identifieras) [4] . Dessutom gäller Tuttas sats i detta fall .

• Toroidformade grafer tillåter bokkapsling med maximalt 7 ark [5] .

• Robertson-Seymour-satsen garanterar att toroidformade grafer kan definieras av en ändlig uppsättning förbjudna grafer. Men uppsättningen av förbjudna grafer i detta fall är okänd, och deras antal är minst 250815 [6] .

Exempel

• Varje graf med skärningsnummer lika med 1 är toroidform.
  • I synnerhet är sådana den fullständiga grafen och den fullständiga tvådelade grafen (" grafen för hus och brunnar ") och alla andra Möbius-stegar .
• komplett graf ,
• komplett tvådelat diagram ,
• greve av Petersen ,
• Earl of Heawood ,
• Möbius-Cantor graf [7] ,
• en av Blanuchis snarkar [8] .

Se även

• Plan graf
• Topologisk grafteori
• Chasar polyeder

Anteckningar

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 .

Länkar

• Chartrand, Gary; Zhang Ping. Kromatisk grafteori. - CRC Press, 2008. - ISBN 978-1-58488-800-0 .
• Endo, Toshiki. Sidantalet för toroidformade grafer är högst sju // 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. Diskreta enformar på maskor och applikationer för 3D-mesh-parameterisering // Computer Aided Geometric Design. - 2006. - Vol. 23, nr. 2. - S. 83-112. - doi : 10.1016/j.cagd.2005.05.002 .
• Heawood P. J.  Kartfärgsättningssatser // Quarterly J. Math. Oxford Ser. - 1890. - Vol. 24. - s. 322-339.
• Kocay W., Neilson D., Szypowski R.  Rita grafer på torus  // Ars Combinatoria. - 2001. - Vol. 59. - S. 259-277. Arkiverad från originalet den 24 december 2004.
• Kronk, Hudson V.; White, Arthur T.  A 4-color theorem for toroidal graphs // Proceedings of the American Mathematical Society . - 1972. - Vol. 34, nr. 1. - S. 83-86. - doi : 10.2307/2037902 .
• Marusic, Dragan; Pisanski, Tomaz.  Den anmärkningsvärda generaliserade Petersen-grafen G (8,3)  // Math. Slovaca. - 2000. - Vol. 50. - S. 117-121.  (inte tillgänglig länk)
• Myrvold, Wendy; Woodcock, Jennifer. En stor uppsättning torushinder och hur de upptäcktes. - 2018. - Vol. 25. doi : 10.37236/3797 .
• Neufeld, Eugene; Myrvold, Wendy. Praktisk toroidalitetstestning // Proceedings of the Eightth Annual ACM-SIAM Symposium on Discrete Algorithms. - 1997. - S. 574-580.
• Orbanic, Alen; Pisanski, Tomaz; Randic, Milan; Servatius, Brigitte. Blanuša dubbel // Math. kommun. - 2004. - Vol. 9, nr. 1. - S. 91-103.