El teorema de Koebe-Andreev-Thurston da una caracterización de los grafos planos en términos de círculos disjuntos tangentes. Para cada grafo plano $G$ existe un empaquetamiento de círculos cuyo grafo es G. ¿Qué ocurre cuando se sustituyen los círculos por esferas? ¿Por esferas de mayor dimensión? ¿Qué se sabe de los grafos que se forman en este caso? Sé que deben contener todos los grafos planos, pero eso es todo.
Permítanme actualizar esto. Basándome en la respuesta a esta pregunta estoy empezando a pensar en el número máximo cromático de este grafo. Si su densidad de aristas es menor que 7 entonces para todos los grafos de este tipo debe existir un punto con 13 o menos aristas. Supongamos que existe un grafo de este tipo con número cromático mayor que 14 entonces busquemos un grafo con el mínimo número de puntos con número cromático mayor que 14. Un punto debe tener 13 o menos aristas. Quítalo y como el grafo tenía el mínimo número de puntos para tener número cromático mayor que 14 el nuevo grafo debe tener número cromático 14 o menos. Coloréalo con 14 colores o menos. Añadimos el punto eliminado y miramos los colores de los trece puntos con los que está adyacente y le damos el color restante, entonces tenemos una coloración 14 del grafo y por tanto una contradicción. Así que el número cromático debe ser 14 o menos. Tenemos un límite inferior de 4 ya que los grafos de esferas tangentes contienen los grafos de círculos tangentes que son los grafos planos que contienen grafos con número cromático cuatro.
A medida que aumentamos las dimensiones de las esferas tangentes el número cromático va al infinito sólo hay que tomar $d+1$ esferas tangentes. Pero creo que podemos hacerlo mejor que eso, por un lado deberíamos ser capaces de mejorar el límite inferior de 4. También creo que debe haber ejemplos de celosías que dan mejores límites inferiores en el número cromático posiblemente exponencial.
Finalmente basándome en los números cromáticos existentes me pregunto si es posible responder a esta pregunta. ¿Existe alguna dimensión en la que el número cromático del grafo de la distancia unitaria sea diferente del número cromático de los grafos de esa dimensión de las esferas tangentes? El grafo de la distancia unitaria es el conjunto de todos los puntos de la $n$ -espacio dimensional con dos puntos conectados si su distancia es uno. Para la dimensión dos, se sabe que el número cromático está en el intervalo de 4 a 7. Para la dimensión tres, el intervalo es de 6 a 15. Para la dimensión tres, el intervalo es de 6 a 15. Para las gráficas de los círculos tangentes tenemos un número cromático de 4 y para las esferas un rango de 4 a 15. Por tanto, aún no se ha eliminado la posibilidad de que los números cromáticos de los dos tipos de grafos sean iguales. Así que la pregunta concreta es qué se sabe y qué se puede demostrar sobre el número cromático de los grafos de las esferas tangentes.
