| Title:
|
Paths with restricted degrees of their vertices in planar graphs (English) |
| Author:
|
Jendroľ, Stanislav |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
49 |
| Issue:
|
3 |
| Year:
|
1999 |
| Pages:
|
481-490 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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\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$. (English) |
| MSC:
|
05C35 |
| MSC:
|
05C38 |
| idZBL:
|
Zbl 1003.05055 |
| idMR:
|
MR1708382 |
| . |
| Date available:
|
2009-09-24T10:24:37Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127504 |
| . |
| Reference:
|
[1] O. V. Borodin: On the total coloring of planar graphs.J. Reine Ange. Math. 394 (1989), 180–185. Zbl 0653.05029, MR 0977440 |
| Reference:
|
[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. Zbl 0705.05023, MR 1100031 |
| Reference:
|
[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, MR 1170097 |
| Reference:
|
[4] O. V. Borodin: Joint extension of two theorems of Kotzig on $3$–polytopes.Combinatorica 13 (1993), 121–125. Zbl 0777.05050, MR 1221181, 10.1007/BF01202794 |
| Reference:
|
[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, MR 1312443, 10.1016/0012-365X(94)E0144-7 |
| Reference:
|
[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 1302363 |
| Reference:
|
[7] B. Grünbaum: Acyclic colorings of planar graphs.Israel J. Math. 14 (1973), 390–408. MR 0317982, 10.1007/BF02764716 |
| Reference:
|
[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 0406868 |
| Reference:
|
[9] B. Grünbaum: New views on some old questions of combinatorial geometry.Int. Teorie Combinatorie, Rome, 1973 1 (1976), 451–468. MR 0470861 |
| Reference:
|
[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 0806977 |
| Reference:
|
[11] J. Harant, S. Jendroľ and M. Tkáč: On 3-connected plane graphs without triangular faces.J. Combinatorial Theory B (to appear). MR 1710537 |
| Reference:
|
[12] M. Horňák and S. Jendroľ: Unavoidable sets of face types for planar maps.Discussiones Math. Graph Theory 16 (1996), 123–141. MR 1446351, 10.7151/dmgt.1028 |
| Reference:
|
[13] J. Ivančo: The weight of a graph.Ann. Discrete Math. 51 (1992), 113–116. MR 1206252, 10.1016/S0167-5060(08)70614-9 |
| Reference:
|
[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 1218205 |
| Reference:
|
[15] S. Jendroľ and Z. Skupień: Local structures in plane maps and distance colourings.Discrete Math. (to appear). MR 1830608 |
| Reference:
|
[16] E. Jucovič: Strengthening of a theorem about $3$–polytopes.Geom. Dedicata 3 (1974), 233–237. MR 0348629, 10.1007/BF00183214 |
| Reference:
|
[17] A. Kotzig: Contribution to the theory of Eulerian polyhedra.Mat.-Fyz. Časopis Sloven. Akad. Vied 5 (1955), 101–113. (Slovak) MR 0074837 |
| Reference:
|
[18] A. Kotzig: On the theory of Euler polyhedra.Mat.-Fyz. Časopis Sloven. Akad. Vied 13 (1963), 20–31. (Russian) MR 0162176 |
| Reference:
|
[19] A. Kotzig: Extremal polyhedral graphs.Ann. New York Acad. Sci. 319 (1979), 569–570. |
| Reference:
|
[20] H. Lebesgue: Quelques conséquences simples de la formule d’Euler.J. Math. Pures Appl. 19 (1940), 19–43. Zbl 0024.28701, MR 0001903 |
| Reference:
|
[21] O. Ore: The Four-Color Problem.Academic Press, New York, 1967. Zbl 0149.21101, MR 0216979 |
| Reference:
|
[22] J. Zaks: Extending Kotzig’s theorem.Israel J. Math. 45 (1983), 281–296. Zbl 0524.05031, MR 0720304, 10.1007/BF02804013 |
| . |
