zbMATH — the first resource for mathematics

Structural properties of planar maps with the minimal degree 5. (English) Zbl 0776.05035
Given a planar map of minimal degree 5, let \(e_{i,j}\) denote the number of edges connecting a vertex of degree \(i\) with a vertex of degree \(j\) and let \(f_{i,j,k}\) denote the number of 3-faces whose vertices have the degrees \(i,j,k\), respectively. Then, if the planar map contains at least one 3-face, the following inequalities hold:
(1) \({18\over 7}e_{5,5}+e_{5,6}\geq 60\),
(2) \(2e_{5,5}+e_{5,6}+{2\over 7}e_{5,7}\geq 60\),
(3) \(18f_{5,5,5}+9f_{5,5,6}+5f_{5,5,7}+4f_{5,6,6}\geq 144\).

05C10 Planar graphs; geometric and topological aspects of graph theory
57M15 Relations of low-dimensional topology with graph theory
Full Text: DOI
[1] Appel, The solution of the four-color-map problem, Scientific American 237 pp 108– (1977)
[2] Borodin, Solution for Kotzig’s and Grünbaum’s problems on the separability of a cycle in planar graphs, Mat. zametki 46 pp 9– (1989)
[3] Franklin, The four color problem, Amer. J. Math. 44 pp 225– (1922) · JFM 48.0664.02
[4] Grünbaum, Acyclic colorings of planar graphs, Israel J. Math. 14 pp 390– (1973) · Zbl 0265.05103
[5] Grünbaum, Polytopal graphs, Math. Assoc. of America Studies in Math. 12 pp 201– (1975) · Zbl 0323.05104
[6] Grünbaum, Analogues for tilings of Kotzig’s theorem on minimal weight of edges, Ann. Discrete Math. 12 pp 129– (1982) · Zbl 0504.05026
[7] Kotzig, From the theory of Euler’s polyhedrons, Mat. cas. 13 pp 20– (1963) · Zbl 0134.19601
[8] A. Kotzig Extremal polyhedral graphs, Proc. Sec. Int. Conf. Combin. Math. (New York) 1978 569 570 · Zbl 0413.05054
[9] Lebesgue, Quelques conséquences simples de la formule d’Euler, J. de Math. Pures Appl. 19 pp 27– (1940) · Zbl 0024.28701
[10] M. D. Plummer On the cyclic connectivity of planar graphs, Graph Theory and Applications (Berlin) 1972 235 242
[11] Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 pp 413– (1904) · JFM 35.0511.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.