Heawood numero

Pinnan Heawood-luku on  tietty yläraja värien enimmäismäärälle, joka tarvitaan minkä tahansa pintaan upotetun graafin värittämiseen . Vuonna 1890 Heawood osoitti, että korkeintaan kaikille pinnoille paitsi pallolle

värit ovat välttämättömiä minkä tahansa graafin värjäykseen upotettuna pintaan, jossa on Euler-ominaisuus [1] . Pallotapaus vastaa neliväristä olettamusta , jonka Kenneth Appel ja Wolfgang Haken osoittivat vuonna 1976 [2] [3] . Numero tuli tunnetuksi Heawood-numerona vuonna 1976.

Franklin osoitti, että Klein-pulloon upotetun graafin kromaattinen luku voi saavuttaa , mutta ei koskaan ylitä sitä [4] . Myöhemmin Gerhard Ringel ja J.W.T. Youngs osoittivat, että pintaan voidaan upottaa täydellinen kärkigraafi , paitsi jos kyseessä on Klein-pullo [5] . Tämä osoittaa, että Heawood-sidosta ei voida parantaa.

Esimerkiksi täydellinen graafi, jossa on pisteitä, voidaan upottaa torukseen seuraavasti:

Muistiinpanot

  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.

Kirjallisuus