Heawood szám

Egy felület Heawood-száma a felületbe ágyazott grafikonok színezéséhez szükséges színek maximális számának  egy bizonyos felső határa . Heawood 1890-ben a gömb kivételével minden felületre bebizonyította, hogy legfeljebb

színek szükségesek bármely Euler-karakterisztikával rendelkező felületbe ágyazott gráf színezéséhez [1] . A gömbeset a négyszínű sejtésnek felel meg , amelyet Kenneth Appel és Wolfgang Haken igazolt be 1976-ban [2] [3] . A szám Heawood számként vált ismertté 1976-ban.

Franklin bebizonyította, hogy egy Klein-palackba ágyazott gráf kromatikus száma elérheti , de soha nem haladja meg [4] . Később Gerhard Ringel és J.W.T. Youngs bebizonyította, hogy egy teljes csúcsgráf beágyazható egy felületbe, kivéve ha Klein-palackról van szó [5] . Ez azt mutatja, hogy a Heawood-kötés nem javítható.

Például egy teljes gráf csúcsokkal beágyazható egy tóruszba a következőképpen:

Jegyzetek

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

Irodalom