Heawood nummer

I matematik är Heawood -talet för en yta en övre gräns för antalet färger som räcker för att färga alla grafer som är inbäddade i ytan.

År 1890 visade Heawood för alla ytor utom sfären att inte mer än

$H(S)=\left\lfloor {\frac {7+{\ sqrt {49-24e(S)}}}{2}}\right\rfloor =\left\lfloor {\frac {7+{\sqrt {1+48g(S)}}}{2}}\right\ rfloor$

färger behövs för att färga vilken graf som helst som är inbäddad i en yta med Euler-karakteristiken ${\displaystyle e(S)} ,$ eller genus $g(S)$ för en orienterbar yta. Siffran $H(S)$ blev känd som Heawood-nummer 1976.

En 6-färgad Klein-flaska, det enda undantaget från Heawood-förmodan

Franklin bevisade att det kromatiska talet för en graf inbäddad i Klein-flaskan kan vara så stort som ${\displaystyle 6} ,$ men aldrig överstiga $6$ . Senare bevisades det i verk av Gerhard Ringel , JWT Youngs och andra bidragsgivare att den fullständiga grafen med $H(S)$ hörn kan bäddas in i ytan $S$ om inte ${ \displaystyle S}$ är Klein-flaskan . Detta fastställde att Heawoods gräns inte kunde förbättras.

Till exempel kan hela grafen på $7$ hörn bäddas in i torusen enligt följande:

Fallet med sfären är den fyrfärgade gissningen , som avgjordes av Kenneth Appel och Wolfgang Haken 1976.

Anteckningar

•   Béla Bollobás , Graph Theory: An Introductory Course , Graduate Texts in Mathematics, volym 63, Springer-Verlag, 1979. Zbl 0411.05032 .
•   Thomas L. Saaty och Paul Chester Kainen ; Fyrfärgsproblemet: Assaults and Conquest , Dover, 1986. Zbl 0463.05041 .

Den här artikeln innehåller material från Heawood-nummer på PlanetMath , som är licensierad under Creative Commons Attribution/Share-Alike-licensen .