Toroidform - Toroidal graph

En kubisk graf med 14 hörn inbäddade i en torus
Den Heawood diagram och tillhörande karta inbäddad i torus.

I matematik är ett toroiddiagram ett diagram som kan bäddas in i en torus . Med andra ord kan grafens hörn placeras på en torus så att inga kanter korsar.

Exempel

Varje graf som kan bäddas in i ett plan kan också bäddas in i en torus. En toroiddiagram av släkt 1 kan inbäddas i en torus men inte i ett plan. Den Heawood graf , den fullständiga grafen K 7 (och därmed K 5 och K 6 ), varvid den Petersen grafen (och följaktligen komplett bipartit graf K 3,3 , eftersom Petersen grafen innehåller en underavdelning av det), en av de Blanusa snarks och alla Möbius-stegar är toroidformade. Mer allmänt är alla diagram med korsning nummer 1 toroidformade. Vissa grafer med större korsnummer är också toroidformade: Möbius – Kantor-diagrammet har till exempel korsningsnummer 4 och är toroidformat.

Egenskaper

Varje toroiddiagram har högst kromatiskt tal 7. Hela grafen K 7 ger ett exempel på toroiddiagram med kromatiskt nummer 7.

Varje triangelfri toroiddiagram har högst kromatiska tal 4.

Genom ett resultat som är analogt med Fárys teorem kan varje toroiddiagram ritas med raka kanter i en rektangel med periodiska gränsförhållanden . Dessutom gäller analogen till Tuttes vårsats i detta fall. Toroidala grafer har också bokinbäddningar med högst 7 sidor.

Hinder

Av Robertson-Seymour theorem , existerar det en ändlig mängd H av minimala icke-toroid grafer, så att en graf är toroidformad, om och endast om den inte har någon graf moll i H . Det vill säga H bildar en uppsättning förbjudna minderåriga för de toroidformade graferna. Hela uppsättningen H är inte känd, men den har minst 17 523 grafer. Alternativt finns det minst 250 815 icke-toroidala grafer som är minimala i den topologiska mindre ordningen. En graf är toroid om och endast om den inte har någon av dessa grafer som en topologisk minor.

Galleri

Se även

Anteckningar

Referenser

  • Chartrand, Gary ; Zhang, Ping (2008), Kromatisk grafteori , CRC Press, ISBN 978-1-58488-800-0.
  • Endo, Toshiki (1997), "Sidantalet för toroidformade grafer är högst sju", Diskret matematik , 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" (PDF) , Computer Aided Geometric Design , 23 (2): 83–112, doi : 10.1016 / j.cagd.2005.05.002 , MR  2189438.
  • Heawood, PJ (1890), "Map colouring theorems", Quarterly Journal of Mathematics , First Series, 24 : 322–339.
  • Kocay, W .; Neilson, D .; Szypowski, R. (2001), "Drawing charts on the torus" (PDF) , Ars Combinatoria , 59 : 259–277, MR  1832459 , arkiverad från originalet (PDF) 2004-12-24 , hämtad 2018-09- 06.
  • 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), "Den anmärkningsvärda generaliserade Petersen-grafen G (8,3)" , Math. Slovaca , 50 : 117–121.
  • Myrvold, Wendy ; Woodcock, Jennifer (2018), "En stor uppsättning torushinder och hur de upptäcktes", Electronic Journal of Combinatorics , 25 (1): P1.16, doi : 10.37236 / 3797
  • Neufeld, Eugene; Myrvold, Wendy (1997), "Practical toroidality testing", Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , s. 574–580.
  • Orbanić, Alen; Pisanski, Tomaž ; Randić, Milano ; Servatius, Brigitte (2004), "Blanuša double", Math. Kommun. , 9 (1): 91–103.