Heawood nummer

Heawood-talet för en yta  är en viss övre gräns för det maximala antalet färger som behövs för att färga en graf som är inbäddad i ytan. År 1890 bevisade Heawood , för alla ytor utom sfären , att som mest

färger är nödvändiga för att färga alla grafer som är inbäddade i en yta med Euler-karakteristik [1] . Sfärfallet motsvarar den fyrfärgade gissningen , som bevisades av Kenneth Appel och Wolfgang Haken 1976 [2] [3] . Numret blev känt som Heawood-numret 1976.

Franklin bevisade att det kromatiska numret för en graf inbäddad i en Klein-flaska kan nå , men aldrig överstiga det [4] . Det bevisades senare av Gerhard Ringel och J.W.T. Youngs att en komplett vertexgraf kan bäddas in i en yta förutom när det är en Klein-flaska [5] . Detta visar att Heawood-gränsen inte kan förbättras.

Till exempel kan en komplett graf med hörn bäddas in i en torus enligt följande:

Anteckningar

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

Litteratur