Número de madera

El número de Heawood de una superficie  es un cierto límite superior en el número máximo de colores necesarios para colorear cualquier gráfico incrustado en la superficie. En 1890 , Heawood probó, para todas las superficies excepto la esfera , que a lo sumo

colors es necesario para colorear cualquier gráfico incrustado en una superficie con característica de Euler [1] . El caso de la esfera corresponde a la conjetura de los cuatro colores , que fue probada por Kenneth Appel y Wolfgang Haken en 1976 [2] [3] . El número se hizo conocido como el número de Heawood en 1976.

Franklin demostró que el número cromático de un gráfico incrustado en una botella de Klein puede llegar a , pero nunca lo supera [4] . Más tarde, Gerhard Ringel y J.W.T. Youngs demostraron que un gráfico de vértice completo se puede incrustar en una superficie, excepto cuando se trata de una botella de Klein [5] . Esto demuestra que el límite de Heawood no se puede mejorar.

Por ejemplo, un gráfico completo con vértices se puede incrustar en un toro de la siguiente manera:

Notas

  1. ↑ Heawood, 1890 , pág. 322–339.
  2. ↑ Appel, Haken, 1977 , pág. 429–490.
  3. ↑ Appel, Haken, Koch, 1977 , pág. 491–567.
  4. ↑ Franklin, 1934 , pág. 363–379.
  5. ↑ Ringel, Youngs, 1968 , pág. 438–445.

Literatura