×

Describing 3-paths in normal plane maps. (English) Zbl 1280.05026

Summary: We prove that every normal plane map, as well as every 3-polytope, has a path on three vertices whose degrees are bounded from above by one of the following triplets: (\(3,3,\infty \)), (\(3,4,11\)), (\(3,7,5\)), (\(3,10,4\)), (\(3,15,3\)), (\(4,4,9\)), (\(6,4,8\)), (\(7,4,7\)), and (\(6,5,6\)). No parameter of this description can be improved, as shown by appropriate 3-polytopes.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C22 Signed and weighted graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[2] Borodin, O. V., On the total coloring of planar graphs, J. Reine Angew. Math., 394, 180-185 (1989) · Zbl 0653.05029
[3] Borodin, O. V., Joint extension of two Kotzig’s theorems on 3-polytopes, Combinatorica, 13, 1, 121-125 (1992)
[4] Borodin, O. V., Precise lower bounds for the number of edges of minor weight in planar maps, Math. Slovaca, 42, 2, 129-142 (1992) · Zbl 0767.05039
[5] Borodin, O. V., The structure of neighborhoods of an edge in planar graphs and the simultaneous coloring of vertices, edges and faces, Mat. Zametki, 53, 5, 35-47 (1993), (in Russian)
[6] Borodin, O. V., Minimal vertex degree sum of a 3-path in plane maps, Discuss. Math. Graph Theory, 17, 2, 279-284 (1997) · Zbl 0906.05017
[7] Franklin, Ph., The four-color problem, Amer. J. Math., 44, 225-236 (1922) · JFM 48.0664.02
[8] Grünbaum, B., New views on some old questions of combinatorial geometry, (Int. Teorie Combinatorie, Rome, (1973), Vol. 1 (1976)), 451-468
[9] Jendrol’, S., A structural property of convex 3-polytopes, Geom. Dedicata, 68, 91-99 (1997) · Zbl 0893.52007
[10] Jendrol’, S., Paths with restricted degrees of their vertices in planar graphs, Czechoslovak Math. J., 49, 124, 481-490 (1999) · Zbl 1003.05055
[11] Kotzig, A., Contribution to the theory of Eulerian polyhedra, Mat. Čas., 5, 101-103 (1955), (in Slovak)
[12] Lebesgue, H., Quelques conséquences simples de la formule d’Euler, J. Math. Pures Appl., 19, 27-43 (1940) · JFM 66.0736.03
[13] Steinitz, E., Polyeder und Raumeinteilungen, Enzykl. Math. Wiss., 3, 1-139 (1922)
[14] Wernicke, P., Über den kartographischen Vierfarbensatz, Math. Ann., 58, 413-426 (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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.