Heawood nummer
Heawood-talet för en yta är en viss övre gräns för det maximala antalet färger som behövs för att färga en graf som är inbäddad i ytan. År 1890 bevisade Heawood , för alla ytor utom sfären , att som mest
färger är nödvändiga för att färga alla grafer som är inbäddade i en yta med Euler-karakteristik [1] . Sfärfallet motsvarar den fyrfärgade gissningen , som bevisades av Kenneth Appel och Wolfgang Haken 1976 [2] [3] . Numret blev känt som Heawood-numret 1976.
Franklin bevisade att det kromatiska numret för en graf inbäddad i en Klein-flaska kan nå , men aldrig överstiga det [4] . Det bevisades senare av Gerhard Ringel och J.W.T. Youngs att en komplett vertexgraf kan bäddas in i en yta förutom när det är en Klein-flaska [5] . Detta visar att Heawood-gränsen inte kan förbättras.
Till exempel kan en komplett graf med hörn bäddas in i en torus enligt följande:
Anteckningar
- ↑ Heawood, 1890 , sid. 322–339.
- ↑ Appel, Haken, 1977 , sid. 429–490.
- ↑ Appel, Haken, Koch, 1977 , sid. 491–567.
- ↑ Franklin, 1934 , sid. 363–379.
- ↑ Ringel, Youngs, 1968 , sid. 438–445.
Litteratur
- Bela Bollobas. Grafteori: En introduktionskurs. - Springer-Verlag, 1979. - T. volym 63. - (GTM). - ISBN 0-387-90399-2 .
- Thomas L. Saaty, Paul Chester Kainen. Fyrfärgsproblemet: överfall och erövring. — Dover, 1986.
- Heawood PJ Kartfärgsättningssatser // Quarterly J. Math. Oxford Ser .. - 1890. - T. 24 .
- Kenneth Appel, Wolfgang Haken. Varje plan karta är fyra färgbar. I. Discharging // Illinois Journal of Mathematics. - 1977. - T. 21 , nr. 3 .
- Kenneth Appel, Wolfgang Haken, John Koch. Varje plan karta är fyra färgbar. II. Reducibility // Illinois Journal of Mathematics. - 1977. - T. 21 , nr. 3 .
- Franklin P. A Sex Color Problem // Journal of Mathematics and Physics. - 1934. - T. 13 , nr. 1–4 . - doi : 10.1002/sapm1934131363 .
- Gerhard Ringel, Youngs JWT Solution of the Heawood Map-Coloring Problem // Proceedings of the National Academy of Sciences. - 1968. - T. 60 , nr 2 . — ISSN 0027-8424 . - doi : 10.1073/pnas.60.2.438 .