En el campo matemático de la teoría de grafos , un gráfico toroidal es un gráfico que puede incrustarse en un toroide . En otras palabras, los vértices y aristas del gráfico se pueden colocar en un toro de modo que ninguna arista se cruce excepto en un vértice que pertenece a ambos.
Cualquier gráfico que pueda estar incrustado en un plano también puede estarlo en un toroide, por lo que todo gráfico plano también es un gráfico toroidal. Un gráfico toroidal que no se puede incrustar en un plano se dice que tiene género 1.
El gráfico de Heawood , el gráfico completo K 7 (y por tanto K 5 y K 6 ), el gráfico de Petersen (y por tanto el gráfico bipartito completo K 3,3 , ya que el gráfico de Petersen contiene una subdivisión del mismo), uno de los sarcasmos de Blanuša , [1] y todas las escaleras de Möbius son toroidales. De manera más general, cualquier gráfico con el cruce número 1 es toroidal. Algunas gráficas con números de cruce mayores también son toroidales: la gráfica de Möbius-Kantor , por ejemplo, tiene el número de cruce 4 y es toroidal. [2]
Cualquier gráfico toroidal tiene un número cromático 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 4. [5]
Por un resultado análogo al teorema de Fáry , cualquier gráfico toroidal se puede dibujar con bordes rectos en un rectángulo con condiciones de contorno periódicas . [6] Además, en este caso se aplica el análogo del teorema del resorte de Tutte . [7] Los gráficos toroidales también tienen incrustaciones de libros con un máximo de 7 páginas. [8]
Según el teorema de Robertson-Seymour , existe un conjunto finito H de gráficas no toroidales mínimas, tal que una gráfica es toroidal si y sólo si no tiene ninguna gráfica menor en H. Es decir, H forma el conjunto de menores prohibidos para las gráficas toroidales. Se desconoce el conjunto H completo, pero tiene al menos 17.523 gráficos. Alternativamente, hay al menos 250.815 gráficos no toroidales que son mínimos en el orden topológico menor . Una gráfica es toroidal si y solo si no tiene ninguna de estas gráficas como topológica menor. [9]
