×

zbMATH — the first resource for mathematics

Paths with restricted degrees of their vertices in planar graphs. (English) Zbl 1003.05055
Summary: In this paper it is proved that every 3-connected planar graph contains a path on 3 vertices each of which is of degree at most 15 and a path on 4 vertices each of which has degree at most 23. Analogous results are stated for 3-connected planar graphs of minimum degree 4 and 5. Moreover, for every pair of integers \(n\geq 3\), \(k\geq 4\) there is a 2-connected planar graph such that every path on \(n\) vertices in it has a vertex of degree \(k\).

MSC:
05C35 Extremal problems in graph theory
05C38 Paths and cycles
PDF BibTeX Cite
Full Text: DOI EuDML
References:
[1] O. V. Borodin: On the total coloring of planar graphs. J. Reine Ange. Math. 394 (1989), 180-185. · Zbl 0653.05029
[2] O. V. Borodin: Computing light edges in planar graphs. Topics in Combinatorics and Graph Theory, R. Bodendiek, R. Henn (eds.), Physica-Verlag Heidelberg\?r 1990, pp. 137-144. · Zbl 0705.05023
[3] O. V. Borodin: Precise lower bound for the number of edges of minor weight in planar maps. Math. Slovaca 42 (1992), 129-142. · Zbl 0767.05039
[4] O. V. Borodin: Joint extension of two theorems of Kotzig on \(3\)-polytopes. Combinatorica 13 (1993), 121-125. · Zbl 0777.05050
[5] O. V. Borodin: Triangles with restricted degree sum of their boundary vertices in plane graphs. Discrete Math. 137 (1995), 45-51. · Zbl 0814.05030
[6] O. V. Borodin and D. P. Sanders: On light edges and triangles in planar graph of minimum degree five. Math. Nachr. 170 (1994), 19-24. · Zbl 0813.05020
[7] B. Grünbaum: Acyclic colorings of planar graphs. Israel J. Math. 14 (1973), 390-408. · Zbl 0265.05103
[8] B. Grünbaum: Polytopal graphs. Studies in Graph Theory, D. R. Fulkerson (eds.), MAA Studies in Mathematics 12, 1975, pp. 201-224. · Zbl 0323.05104
[9] B. Grünbaum: New views on some old questions of combinatorial geometry. Int. Teorie Combinatorie, Rome, 1973 1 (1976), 451-468.
[10] B. Grünbaum and G. C. Shephard: Analogues for tiling of Kotzig’s theorem on minimal weights of edges. Ann. Discrete Math. 12 (1982), 129-140. · Zbl 0504.05026
[11] J. Harant, S. Jendroľ and M. Tkáč: On 3-connected plane graphs without triangular faces. J. Combinatorial Theory B · Zbl 1027.05030
[12] M. Horňák and S. Jendroľ: Unavoidable sets of face types for planar maps. Discussiones Math. Graph Theory 16 (1996), 123-141. · Zbl 0877.05048
[13] J. Ivančo: The weight of a graph. Ann. Discrete Math. 51 (1992), 113-116. · Zbl 0773.05066
[14] J. Ivančo and S. Jendroľ: On extremal problems concerning weights of edges of graphs. Coll. Math. Soc. J. Bolyai, 60. Sets, Graphs and Numbers, Budapest (Hungary) 1991, North Holland, 1993, pp. 399-410. · Zbl 0790.05045
[15] S. Jendroľ and Z. Skupień: Local structures in plane maps and distance colourings. Discrete Math. · Zbl 0990.05043
[16] E. Jucovič: Strengthening of a theorem about \(3\)-polytopes. Geom. Dedicata 3 (1974), 233-237. · Zbl 0297.52006
[17] A. Kotzig: Contribution to the theory of Eulerian polyhedra. Mat.-Fyz. Časopis Sloven. Akad. Vied 5 (1955), 101-113.
[18] A. Kotzig: On the theory of Euler polyhedra. Mat.-Fyz. Časopis Sloven. Akad. Vied 13 (1963), 20-31. · Zbl 0134.19601
[19] A. Kotzig: Extremal polyhedral graphs. Ann. New York Acad. Sci. 319 (1979), 569-570.
[20] H. Lebesgue: Quelques conséquences simples de la formule d’Euler. J. Math. Pures Appl. 19 (1940), 19-43. · Zbl 0024.28701
[21] O. Ore: The Four-Color Problem. Academic Press, New York, 1967. · Zbl 0149.21101
[22] J. Zaks: Extending Kotzig’s theorem. Israel J. Math. 45 (1983), 281-296. · Zbl 0524.05031
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.