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 7 (y por lo tanto K 5 y K 6 ), 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 7 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 en 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]
