¿Es cierto que el número mínimo de colores para colorear un mapa sigue siendo 4, incluso si la superficie sobre la que se dibuja el mapa es más compleja que una esfera?
¿Y si tenemos Gráficos "planares" en las bandas de Möbius ¿o en un toroide?
Respuestas
¿Demasiados anuncios?
No. La sustitución correcta de $4$ para todas las superficies compactas sin límite, excepto la botella de Klein, viene dada por la Teorema de Ringel-Youngs (antes la conjetura de Heawood): se necesita $$\left\lfloor \frac{7 + \sqrt{49 - 24 \chi}}{2} \right\rfloor$$
colores a excepción de la botella de Klein donde se lleva $6$ , donde $\chi$ es la característica de Euler de la superficie. Para el toro, $\chi = 0$ , por lo que se necesita $7$ colores. No sé la respuesta de la cabeza para una tira de Möbius.
Bryan Roth
Puntos
3592
Aunque otros ya han dado respuestas más ambiciosas, todavía puede valer la pena explicar por qué el "pensamiento puro" muestra que la respuesta a la pregunta del PO en el primer párrafo debe ser no .
La observación clave es la siguiente: todo gráfico finito puede estar incrustado en alguna subsuperficie de $\mathbb{R}^3$ . Para ello, se debe comenzar con un Inmersión planar 2:1 del gráfico, es decir, un mapa que es localmente una incrustación en el plano en global tiene, en el peor de los casos, dos aristas que se cruzan en cualquier punto. (Es un ejercicio fácil demostrar que tales cosas existen para cualquier grafo finito). Ahora imaginemos que el grafo es el plano de una autopista: será una mala idea que la autopista tenga auto-intersecciones, así que ¿qué hacemos? Bueno, como en el mundo real, siempre que la autopista se cruce a sí misma, podemos construir un paso elevado levantando una rama hacia la tercera dimensión para que no se cruce con la otra. En términos topológicos, añadimos un asa al plano en el que está incrustado el gráfico. Así conseguimos incrustar el gráfico en una superficie, que es de hecho el $g$ -(donde $g$ es el número de cruces del plano) menos un solo punto (porque estamos empezando con el plano en lugar de la $2$ -esfera).
[Este argumento demuestra en realidad algo cuantitativo: definimos el número de cruce de un grafo finito sea el número mínimo de cruces en cualquier $2:1$ inmersión planar, y definimos el género de incrustación de un gráfico finito sea el género mínimo de una superficie compacta en la que $G$ (por tanto, los grafos planos son precisamente los de género cero). Entonces el argumento anterior muestra que el género de incrustación de $G$ es menor o igual que el número de cruce de $G$ .]
Para cualquier $n \in \mathbb{Z}^+$ el gráfico completo $K_n$ tiene un número cromático $n$ . Así, los números de coloración del mapa de una superficie orientable compacta de género $g$ debe tender a infinito con $g$ . (La fórmula precisa se da en la respuesta de Qiaochu.) De hecho, en el mismo artículo de 1968 en el que demostraron la Conjetura de Heawood, Ringel y Youngs dieron una fórmula precisa para el género de incrustación de $K_n$ : para $n \geq 3$ es $\frac{(n-3)(n-4)}{12}$ . (Claramente es $0$ para $1 \leq n \leq 4$ .)
Observaciones:
1) Digo "género de incrustación" cuando la mayoría de los teóricos de los grafos dicen "género". Como geómetra aritmético que se encuentra con los grafos al estudiar la degeneración de las curvas algebraicas, reservo el término "género" de un grafo para lo que se llama clásicamente el número ciclomático es decir, el primer número de Betti del complejo celular correspondiente.
2) Sé menos sobre este tema de lo que la respuesta anterior podría indicar. Por ejemplo, he encontrado el cálculo del género de incrustación de $K_n$ a través de una búsqueda en Internet mientras escribía esta respuesta. En particular, no he leído el artículo de Ringel y Youngs. Si alguien quiere añadir más información sobre este tema, que me eduque en primer lugar...
Attila Lendvai
Puntos
1084
Gracias por actualizar mi código. He dejado este ejemplo de torus fuera de la última edición de mi libro.
Ligeramente relacionado: Mathematica tiene una base de datos ( GraphData ) de más de 6000 gráficos. Acabo de revisar TODOS los planos de esa base de datos y he determinado el número cromático (normalmente 3 o 4). En particular he hecho todos los esqueletos de poliedros y sus duales, motivado por una luminaria (Trubridge) que compré. El algoritmo principal es el método de Kempe, descrito en detalle en mi libro (Mathematica in Action). El uso de ILP (programación entero-lineal) también es posible en grafos de tamaño modesto para determinar los números cromáticos, o los números cromáticos de las aristas, etc. No sé si hay algo especialmente interesante en el caso poliédrico: entre los 1100 números cromáticos que encontré para tales "grafos poliédricos", unos 100 eran 4 y 1100 eran 3. Si quieres más información sobre todo esto, ponte en contacto conmigo.
En el caso de los gráficos de poliedros con nombre, sólo los siguientes eran cuatricromáticos: "IcosahedralGraph" , "PentakisDodecahedralGraph" , "SmallTriakisOctahedralGraph" , "SnubDodecahedralGraph" , "TetrahedralGraph" , "TriakisIcosahedralGraph" , "TriakisTetrahedralGraph" .
En cuanto a la relevancia de la pregunta original, puedo decir que mi implementación de Kempe es bastante rápida para los gráficos planos, habiendo tenido éxito en el gráfico de los 3300 condados de los Estados Unidos. En cuanto a los famosos contraejemplos, conjeturo que siempre se pueden evitar con Kempe simplemente permutando los vértices e intentando de nuevo si se llega a un punto muerto.
Stan Wagon (vagón en macalester d o t e d u )
Andrew
Puntos
140
Aparentemente, ese código para colorear con 7 colores un toro de El libro de Wagon del que hablaba en los comentarios es un poco antiguo; aquí hay una actualización para las versiones más nuevas de Mathematica :
spiral[theta0_, theta1_, phi0_, phi1_, color_] :=
ParametricPlot3D[{
(4 + Cos[1/143 (144 phi + 12 theta)]) Cos[1/143 (12 phi + 144 theta)],
(4 + Cos[1/143 (144 phi + 12 theta)]) Sin[1/143 (12 phi + 144 theta)],
Sin[1/143 (144 phi + 12 theta)]},
{theta, theta0, theta1}, {phi, phi0, phi1},
Mesh -> False, PlotStyle -> color]
Show[
spiral[Pi/12, (21*Pi)/12, Pi/3, 2*Pi, White],
spiral[-((3*Pi)/12), -(Pi/12), Pi/2, (13*Pi)/6, Green],
spiral[-(Pi/12), Pi/12, Pi/3, 2*Pi, Brown],
spiral[-(Pi/6), 0, Pi/6, Pi/3, Yellow],
spiral[Pi/6, (23*Pi)/12, Pi/6, Pi/3, Blue],
spiral[0, Pi/6, Pi/6, Pi/3, Purple],
spiral[Pi/12, (11*Pi)/6, 0, Pi/6, Red],
Axes -> None, Boxed -> False, Lighting -> "Neutral",
PlotRange -> All, ViewPoint -> {2, 0.2, 1.2}]
