Heawoodovo číslo

Heawoodovo číslo povrchu  je určitá horní hranice maximálního počtu barev potřebných k obarvení jakéhokoli grafu vloženého do povrchu. V roce 1890 Heawood dokázal pro všechny povrchy kromě koule , že nanejvýš

barvy jsou nezbytné pro obarvení jakéhokoli grafu vloženého do plochy s Eulerovou charakteristikou [1] . Případ koule odpovídá čtyřbarevné domněnce , kterou dokázali Kenneth Appel a Wolfgang Haken v roce 1976 [2] [3] . Číslo se stalo známým jako Heawoodovo číslo v roce 1976.

Franklin dokázal, že chromatické číslo grafu vloženého do Kleinovy ​​láhve může dosáhnout , ale nikdy ho nepřekročí [4] . Později bylo prokázáno Gerhardem Ringelem a J.W.T. Youngsem, že do povrchu lze vložit úplný vrcholový graf, pokud se nejedná o Kleinovu láhev [5] . To ukazuje, že vazbu Heawood nelze zlepšit.

Například úplný graf s vrcholy lze vložit do torusu takto:

Poznámky

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

Literatura