Número de Heawood

Límite superior para el número de colores que son suficientes para colorear cualquier gráfico

En matemáticas , el número de Heawood de una superficie es un límite superior para la cantidad de colores suficientes para colorear cualquier gráfico incrustado en la superficie.

En 1890, Heawood demostró que para todas las superficies, excepto la esfera , no se podía alcanzar más de

${\displaystyle H(S)=\left\lfloor {\frac {7+{\sqrt {49-24e(S)}}}{2}}\right\rfloor =\left\lfloor {\frac {7+{\sqrt {1+48g(S)}}}{2}}\right\rfloor }$

Se necesitan colores para colorear cualquier gráfico incrustado en una superficie de característica de Euler , o género para una superficie orientable. ^[1] El número se conoció como número de Heawood en 1976. ${\displaystyle e(S)}$ ${\displaystyle g(S)}$ ${\displaystyle H(S)}$

Una botella de Klein de seis colores, la única excepción a la conjetura de Heawood

Franklin demostró que el número cromático de un grafo incrustado en la botella de Klein puede ser tan grande como , pero nunca excede . ^[2] Más tarde se demostró en los trabajos de Gerhard Ringel , JWT Youngs y otros contribuyentes que el grafo completo con vértices puede incrustarse en la superficie a menos que sea la botella de Klein . ^[3] Esto estableció que el límite de Heawood no podía mejorarse. ${\displaystyle 6}$ ${\displaystyle 6}$ ${\displaystyle H(S)}$ ${\displaystyle S}$ ${\displaystyle S}$

Por ejemplo, el gráfico completo de vértices se puede incrustar en el toro de la siguiente manera: ${\displaystyle 7}$

El caso de la esfera es la conjetura de los cuatro colores , que fue resuelta por Kenneth Appel y Wolfgang Haken en 1976. ^{[4] [5]}

Notas

• Béla Bollobás , Teoría de grafos: un curso introductorio , Textos de posgrado en matemáticas, volumen 63, Springer-Verlag, 1979. Zbl  0411.05032.
• Thomas L. Saaty y Paul Chester Kainen ; El problema de los cuatro colores: asaltos y conquista , Dover, 1986. Zbl  0463.05041.

Este artículo incorpora material del número de Heawood en PlanetMath , que está licenciado bajo la Licencia Creative Commons Atribución/Compartir-Igual .

Referencias

1. PJ Heawood (1890), "Teoremas de coloración de mapas", Quarterly J. Math. , 24 : 322–339
2. P. Franklin (1934), "Un problema de seis colores", Journal of Mathematics and Physics , 13 (1–4): 363–379, doi :10.1002/sapm1934131363
3. Gerhard Ringel; JWT Youngs (1968), "Solución del problema de coloración de mapas de Heawood", Actas de la Academia Nacional de Ciencias , 60 (2): 438–445, Bibcode :1968PNAS...60..438R, doi : 10.1073/pnas.60.2.438 , ISSN  0027-8424, PMC 225066 , PMID  16591648 
4. Kenneth Appel; Wolfgang Haken (1977), "Cada mapa planar es coloreable en cuatro dimensiones. I. Descargas", Illinois Journal of Mathematics , 21 (3): 429–490, MR  0543792
5. Kenneth Appel; Wolfgang Haken; John Koch (1977), "Cada mapa planar es coloreable en cuatro dimensiones. II. Reducibilidad", Illinois Journal of Mathematics , 21 (3): 491–567, doi : 10.1215/ijm/1256049012 , MR  0543793