Heawood nummer

Heawood-tallet for en overflade  er en vis øvre grænse for det maksimale antal farver, der er nødvendige for at farve enhver graf, der er indlejret i overfladen. I 1890 beviste Heawood , for alle overflader undtagen kuglen , at højst

farver er nødvendige for at farve enhver graf, der er indlejret i en overflade med Euler-karakteristik [1] . Kuglehuset svarer til den firefarvede formodning , som blev bevist af Kenneth Appel og Wolfgang Haken i 1976 [2] [3] . Nummeret blev kendt som Heawood-nummeret i 1976.

Franklin beviste, at det kromatiske tal for en graf indlejret i en Klein-flaske kan nå , men aldrig overskride det [4] . Det blev senere bevist af Gerhard Ringel og J.W.T. Youngs, at en komplet vertex-graf kan indlejres i en overflade, undtagen når det er en Klein-flaske [5] . Dette viser, at Heawood-bindingen ikke kan forbedres.

For eksempel kan en komplet graf med toppunkter indlejres i en torus som følger:

Noter

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

Litteratur