Gráfica toroidal

En el campo matemático de la teoría de grafos , un grafo toroidal es un grafo que se puede incrustar en un toro . En otras palabras, los vértices y las aristas del grafo se pueden colocar en un toro de manera que ninguna arista se intersecte excepto en un vértice que pertenece a ambos.

Cualquier grafo que pueda ser embebido en un plano también puede ser embebido en un toro, por lo que todo grafo plano es también un grafo toroidal. Se dice que un grafo toroidal que no puede ser embebido en un plano tiene género 1.

El grafo de Heawood , el grafo completo K ₇ (y por lo tanto K ₅ y K ₆ ), el grafo de Petersen (y por lo tanto el grafo bipartito completo K _3,3 , ya que el grafo de Petersen contiene una subdivisión de este), uno de los snarks de Blanuša [ ^1] y todas las escaleras de Möbius son toroidales. En términos más generales, cualquier grafo con número de cruces 1 es toroidal. Algunos grafos con números de cruces mayores también son toroidales: el grafo de Möbius-Kantor , por ejemplo, tiene número de cruces 4 y es toroidal. ^[2]

Cualquier gráfico toroidal tiene un número cromático de como máximo 7. ^[3] El gráfico completo K ₇ proporciona un ejemplo de un gráfico toroidal con número cromático 7. ^[4]

Cualquier gráfico toroidal sin triángulos tiene un número cromático como máximo de 4. ^[5]

Por un resultado análogo al teorema de Fáry , cualquier grafo toroidal puede dibujarse con bordes rectos en un rectángulo con condiciones de contorno periódicas . ^[6] Además, el análogo del teorema del resorte de Tutte se aplica en este caso. ^[7] Los grafos toroidales también tienen incrustaciones de libros con un máximo de 7 páginas. ^[8]

Por el teorema de Robertson-Seymour , existe un conjunto finito H de grafos no toroidales mínimos, de modo que un grafo es toroidal si y solo si no tiene ningún grafo menor en H. Es decir, H forma el conjunto de menores prohibidos para los grafos toroidales. El conjunto completo H no se conoce, pero tiene al menos 17.523 grafos. Alternativamente, existen al menos 250.815 grafos no toroidales que son mínimos en el orden de los menores topológicos . Un grafo es toroidal si y solo si no tiene ninguno de estos grafos como menor topológico. ^[9]

• 
  Dos gráficos de Cayley isomorfos del grupo de cuaterniones .
• 
  Gráfico de Cayley del grupo de cuaterniones incrustado en el toro.
• Vídeo del gráfico de Cayley del grupo de cuaterniones incrustado en el toro.
• 
  El gráfico de Pappus y el mapa asociado incrustados en el toro.

• Gráfico planar
• Teoría de grafos topológicos
• Poliedro de Császár

• Chartrand, Gary ; Zhang, Ping (2008), Teoría de grafos cromáticos , CRC Press, ISBN 978-1-58488-800-0.
• Endo, Toshiki (1997), "El número de páginas de los gráficos toroidales es como máximo siete", Discrete Mathematics , 175 (1–3): 87–96, doi :10.1016/S0012-365X(96)00144-6, MR  1475841.
• Gortler, Steven J.; Gotsman, Craig; Thurston, Dylan (2006), "Formas unidimensionales discretas en mallas y aplicaciones a la parametrización de mallas 3D" (PDF) , Computer Aided Geometric Design , 23 (2): 83–112, doi :10.1016/j.cagd.2005.05.002, MR  2189438, S2CID  135438.
• Heawood, PJ (1890), "Teorema del mapa-color", Quarterly Journal of Pure and Applied Mathematics , Primera serie, 24 : 322–339.
• Kocay, W.; Neilson, D.; Szypowski, R. (2001), "Dibujo de gráficos en el toro" (PDF) , Ars Combinatoria , 59 : 259–277, MR  1832459, archivado desde el original (PDF) el 2004-12-24 , consultado el 2018-09-06.
• Kronk, Hudson V.; White, Arthur T. (1972), "Un teorema de 4 colores para gráficos toroidales", Actas de la American Mathematical Society , 34 (1), American Mathematical Society: 83–86, doi :10.2307/2037902, JSTOR  2037902, MR  0291019.
• Marušič, Dragan ; Pisanski, Tomaž (2000), "El notable gráfico generalizado de Petersen G (8,3)", Math. Eslovaca , 50 : 117–121, CiteSeerX  10.1.1.28.7183 , hdl :10338.dmlcz/133137, MR  1763113, Zbl  0984.05044.
• Myrvold, Wendy ; Woodcock, Jennifer (2018), "Un gran conjunto de obstrucciones de toro y cómo se descubrieron", Electronic Journal of Combinatorics , 25 (1): P1.16, doi : 10.37236/3797
• Neufeld, Eugene; Myrvold, Wendy (1997), "Pruebas prácticas de toroidalidad", Actas del octavo simposio anual ACM-SIAM sobre algoritmos discretos , págs. 574–580, ISBN 978-0-89871-390-9.
• Orbanić, Alen; Pisanski, Tomaž ; Randić, Milán ; Servatius, Brigitte (2004), "Blanuša doble" (PDF) , Math. Comunitario. , 9 (1): 91–103, CiteSeerX  10.1.1.361.2772.