Numărul Heawood

Numărul Heawood al unei suprafețe  este o anumită limită superioară a numărului maxim de culori necesare pentru a colora orice grafic încorporat în suprafață. În 1890 , Heawood a dovedit, pentru toate suprafețele, cu excepția sferei , că cel mult

culorile este necesar pentru colorarea oricărui grafic înglobat într-o suprafață cu caracteristica Euler [1] . Cazul sferei corespunde conjecturii cu patru culori , care a fost demonstrată de Kenneth Appel și Wolfgang Haken în 1976 [2] [3] . Numărul a devenit cunoscut sub numele de numărul Heawood în 1976.

Franklin a demonstrat că numărul cromatic al unui grafic încorporat într- o sticlă Klein poate ajunge la , dar nu îl depășește niciodată [4] . Mai târziu a fost dovedit de Gerhard Ringel și J.W.T.Youngs că un grafic de vârf complet poate fi încorporat într-o suprafață, cu excepția cazului în care este o sticlă Klein [5] . Acest lucru arată că legarea Heawood nu poate fi îmbunătățită.

De exemplu, un grafic complet cu vârfuri poate fi încorporat într-un tor după cum urmează:

Note

  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.

Literatură