Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-03T01:34:44.995Z Has data issue: false hasContentIssue false
  • English
  • Français

Map-Colour Theorems

Published online by Cambridge University Press:  20 November 2018

G. A. Dirac
G. A. Dirac*
Affiliation:
University of Toronto
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A map wil be called k-chromatic or said to have chromatic number k if k is the least positive integer having the property that the countries of the map can be divided into k mutually disjoint (colour) classes in such a way that no two countries which have a common frontier line are in the same (colour) class.Heawood [4] proved that for h > 1 the chromatic number of a map on a surface of connectivity h is at most nh, where

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 4 , 1952 , pp. 480 - 490
Copyright
Copyright © Canadian Mathematical Society 1952

References

1. Brooks, R. L., On colouring the nodes of a network, Proc. Cambridge Phil. Soc, vol. 37 (1941), 194.Google Scholar
2. de Bruijn, N. G. and Erdös, P., A colour problem for infinite graphs and a problem in the theory of relations, Proc. K. Nederl. Akad. Wetensch. Amsterdam, ser. A, vol. 54 (1951), 371.Google Scholar
3. Dirac, G. A., Some theorems on abstract graphs, Proc. London Math. Soc. (3), vol. 2 (1952), 69.Google Scholar
4. Heawood, P. J., Map colour theorem, Quarterly J. Math., vol. 24 (1890), 332.Google Scholar
5. For h — 3, 5, 7, 9, 11, 13, 15 see Heffter, L., Über das Problem der Nachbargebiete, Math. Ann., vol. 38 (1891), 477.Google Scholar
For h = 2 seeTietze, H., Einige Bemerkungen Über das Problem des Kartenfärbens aufeinseitigen Flachen, Jber. dtsch. MatVer., vol. 19 (1910), 155;Google Scholar
D. Hilbert and S. Cohn-Vossen, Anschauliche Geometrie (Berlin, 1932), translated as Geometry and the imagination (New York, 1952); W. W. Rouse Ball and H. S. M. Coxeter, Mathematical recreations and essays (London, 1947).Google Scholar
For h = 4 seeKagno, I. N., A note on the Heawood colour formula, J. Math. Phys., vol. 14 (1935), 228.Google Scholar
For h = 6 seeCoxeter, H. S. M., The map colouring of unorientablc surfaces, Duke Math. J., vol. 10 (1943), 293.Google Scholar
For h = 8 seeBose, R. C., On the construction of balanced incomplete block designs, Annals of Eugenics, vol. 9 (1939), 353.Google Scholar
The cases h = 10, 12, 14: The connectivities of the surfaces obtained from the sphere and from the projective plane by attaching n handles are 2n + 1 and 2n + 2 respectively. Any map drawn on the surface of a sphere with n handles attached can also be drawn on a projective plane with n handles attached. It follows that . Hence, by Heffter's results quoted above and by the table on p. 480, Heawood's result is best possible also for h = 10, 12, and 14.Google Scholar