La hipótesis de Heawood

La conjetura de Heawood , o el teorema de Ringel-Yangs, da un límite inferior en el número de colores que se necesitan para colorear un gráfico en una superficie con un género dado . Este límite se denomina número cromático superficial o número de Heawood. Para superficies de género 0, 1, 2, 3, 4, 5, 6, 7, ..., el número requerido de colores es 4, 7, 8, 9, 10, 11, 12, 12, .... A000934 ,.

La hipótesis fue formulada en 1890 por Percy John Heawood y probada en 1968 por Gerhard Ringel y Ted Youngs . Un caso, a saber, la botella de Klein no dirigida , es una excepción a la fórmula general. Se necesitaba un enfoque completamente diferente para el problema mucho más antiguo de encontrar la cantidad de colores necesarios para un plano o una esfera , y fue resuelto en 1976 por Wolfgang Haken y Kennthe Appel ( teorema de los cuatro colores ). En una esfera, el límite inferior es fácil de encontrar, y en superficies de género superior, es fácil encontrar un límite superior, y se demostró en el breve artículo original de Heawood que contenía la formulación de la conjetura. En otras palabras, para probar el teorema de Ringel, Youngs y otros tuvieron que construir ejemplos extremos para cada género de superficie g = 1,2,3,.... Si g = 12s + k, el género de la superficie se divide en 12 casos según al resto k = 0 ,1,2,3,4,5,6,7,8,9,10,11. Años en los que se resolvieron doce casos y quiénes los resolvieron:

Las últimas siete excepciones separadas han sido resueltas:

Declaración formal

Percy John Heawood conjeturó en 1890 que, para un género dado g > 0, el número mínimo de colores necesarios para colorear cualquier dibujo en una superficie orientable de ese género (o, de manera equivalente, para colorear cualquier partición de la superficie en dominios simplemente conectados) es dado por

donde está la función suelo .

El mismo Heawood creyó haber probado la igualdad en la fórmula, pero ya un año después Heffter [1] señaló imprecisiones en la prueba de Heawood, por lo que la desigualdad se mantuvo. Heffter mismo demostró la igualdad para . Como resultado, la afirmación de que la igualdad se cumple en la fórmula de Heawood se conoció como la conjetura de Heawood sobre la coloración de los mapas [2]

Reemplazando el género con la característica de Euler , obtenemos una fórmula que cubre tanto los casos orientables como los no orientables,

Como demostraron Ringel y Youngs, esta igualdad es válida para todas las superficies excepto para la botella de Klein . Philip Franklin demostró 1930 que una botella de Klein necesita un máximo de 6 colores, no 7 como dice la fórmula. El gráfico de Franklin se puede dibujar en la botella de Klein de tal manera que se formen seis regiones limítrofes por pares, lo que muestra que el límite es exacto.

El límite superior probado en el artículo original de Heawood se basa en un algoritmo de coloración codicioso . Al manipular la característica de Euler, se puede demostrar que cualquier gráfico incrustado en una superficie determinada debe tener al menos un vértice con un grado menor que el valor límite especificado. Si eliminamos este vértice y coloreamos el gráfico restante, el pequeño número de aristas que inciden en el vértice eliminado hace posible volver a agregar el vértice y darle un color sin aumentar el número de colores requerido. En la dirección opuesta, la prueba es más complicada, mostrando que en todos los casos (con la excepción de la botella de Klein) se puede incrustar en una superficie un gráfico completo con el número de vértices igual a un número dado de colores.

Ejemplo

Para el toro , g = 1, por lo que χ = 0. Así, como se deduce de la fórmula, cualquier división del toro en regiones puede colorearse en siete colores. La figura muestra una partición del toro, en la que cada una de las siete regiones limita con todas las demás regiones. Esta división muestra que el borde de siete colores es correcto para este caso. Los límites de esta partición forman una incrustación del gráfico de Heawood en el toro.

Notas

  1. ↑ Heffter, 1891 , pág. 477-508.
  2. ↑ Harari, 2003 , pág. 162.

Literatura

Enlaces