Geodesic
Paths with restricted degrees of their vertices in planar graphs
Czechoslovak Mathematical Journal, Tome 49 (1999) no. 3, pp. 481-490

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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\ge 3$, $ k\ge 4$ there is a $2$-connected planar graph such that every path on $n$ vertices in it has a vertex of degree $k$.
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\ge 3$, $ k\ge 4$ there is a $2$-connected planar graph such that every path on $n$ vertices in it has a vertex of degree $k$.
Classification : 05C35, 05C38 
Jendroľ, Stanislav. Paths with restricted degrees of their vertices in planar graphs. Czechoslovak Mathematical Journal, Tome 49 (1999) no. 3, pp. 481-490. http://geodesic.mathdoc.fr/item/CMJ_1999_49_3_a2/
@article{CMJ_1999_49_3_a2,
     author = {Jendro\v{l}, Stanislav},
     title = {Paths with restricted degrees of their vertices in planar graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {481--490},
     year = {1999},
     volume = {49},
     number = {3},
     mrnumber = {1708382},
     zbl = {1003.05055},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_1999_49_3_a2/}
}
TY  - JOUR
AU  - Jendroľ, Stanislav
TI  - Paths with restricted degrees of their vertices in planar graphs
JO  - Czechoslovak Mathematical Journal
PY  - 1999
SP  - 481
EP  - 490
VL  - 49
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/CMJ_1999_49_3_a2/
LA  - en
ID  - CMJ_1999_49_3_a2
ER  - 
%0 Journal Article
%A Jendroľ, Stanislav
%T Paths with restricted degrees of their vertices in planar graphs
%J Czechoslovak Mathematical Journal
%D 1999
%P 481-490
%V 49
%N 3
%U http://geodesic.mathdoc.fr/item/CMJ_1999_49_3_a2/
%G en
%F CMJ_1999_49_3_a2

[1] O. V. Borodin: On the total coloring of planar graphs. J. Reine Ange. Math. 394 (1989), 180–185. | MR | Zbl

[2] O. V. Borodin: Computing light edges in planar graphs. In: Topics in Combinatorics and Graph Theory, R. Bodendiek, R. Henn (eds.), Physica-Verlag Heidelbergȳr 1990, pp. 137–144. | MR | Zbl

[3] O. V. Borodin: Precise lower bound for the number of edges of minor weight in planar maps. Math. Slovaca 42 (1992), 129–142. | MR | Zbl

[4] O. V. Borodin: Joint extension of two theorems of Kotzig on $3$–polytopes. Combinatorica 13 (1993), 121–125. | DOI | MR | Zbl

[5] O. V. Borodin: Triangles with restricted degree sum of their boundary vertices in plane graphs. Discrete Math. 137 (1995), 45–51. | DOI | MR | Zbl

[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. | MR

[7] B. Grünbaum: Acyclic colorings of planar graphs. Israel J. Math. 14 (1973), 390–408. | DOI | MR

[8] B. Grünbaum: Polytopal graphs. In: Studies in Graph Theory, D. R. Fulkerson (eds.), MAA Studies in Mathematics 12, 1975, pp. 201–224. | MR

[9] B. Grünbaum: New views on some old questions of combinatorial geometry. Int. Teorie Combinatorie, Rome, 1973 1 (1976), 451–468. | MR

[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. | MR

[11] J. Harant, S. Jendroľ and M. Tkáč: On 3-connected plane graphs without triangular faces. J. Combinatorial Theory B (to appear). | MR

[12] M. Horňák and S. Jendroľ: Unavoidable sets of face types for planar maps. Discussiones Math. Graph Theory 16 (1996), 123–141. | DOI | MR

[13] J. Ivančo: The weight of a graph. Ann. Discrete Math. 51 (1992), 113–116. | DOI | MR

[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. | MR

[15] S. Jendroľ and Z. Skupień: Local structures in plane maps and distance colourings. Discrete Math. (to appear). | MR

[16] E. Jucovič: Strengthening of a theorem about $3$–polytopes. Geom. Dedicata 3 (1974), 233–237. | DOI | MR

[17] A. Kotzig: Contribution to the theory of Eulerian polyhedra. Mat.-Fyz. Časopis Sloven. Akad. Vied 5 (1955), 101–113. (Slovak) | MR

[18] A. Kotzig: On the theory of Euler polyhedra. Mat.-Fyz. Časopis Sloven. Akad. Vied 13 (1963), 20–31. (Russian) | MR

[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. | MR | Zbl

[21] O. Ore: The Four-Color Problem. Academic Press, New York, 1967. | MR | Zbl

[22] J. Zaks: Extending Kotzig’s theorem. Israel J. Math. 45 (1983), 281–296. | DOI | MR | Zbl