Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
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$.
References:
[1] O. V. Borodin: On the total coloring of planar graphs. J. Reine Ange. Math. 394 (1989), 180–185. MR 0977440 | Zbl 0653.05029
[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 1100031 | 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. MR 1170097 | Zbl 0767.05039
[4] O. V. Borodin: Joint extension of two theorems of Kotzig on $3$–polytopes. Combinatorica 13 (1993), 121–125. DOI 10.1007/BF01202794 | MR 1221181 | 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. DOI 10.1016/0012-365X(94)E0144-7 | MR 1312443 | 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. MR 1302363
[7] B. Grünbaum: Acyclic colorings of planar graphs. Israel J. Math. 14 (1973), 390–408. DOI 10.1007/BF02764716 | MR 0317982
[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
[9] B. Grünbaum: New views on some old questions of combinatorial geometry. Int. Teorie Combinatorie, Rome, 1973 1 (1976), 451–468. MR 0470861
[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
[11] J. Harant, S. Jendroľ and M. Tkáč: On 3-connected plane graphs without triangular faces. J. Combinatorial Theory B (to appear). MR 1710537
[12] M. Horňák and S. Jendroľ: Unavoidable sets of face types for planar maps. Discussiones Math. Graph Theory 16 (1996), 123–141. DOI 10.7151/dmgt.1028 | MR 1446351
[13] J. Ivančo: The weight of a graph. Ann. Discrete Math. 51 (1992), 113–116. DOI 10.1016/S0167-5060(08)70614-9 | MR 1206252
[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
[15] S. Jendroľ and Z. Skupień: Local structures in plane maps and distance colourings. Discrete Math. (to appear). MR 1830608
[16] E. Jucovič: Strengthening of a theorem about $3$–polytopes. Geom. Dedicata 3 (1974), 233–237. DOI 10.1007/BF00183214 | MR 0348629
[17] A. Kotzig: Contribution to the theory of Eulerian polyhedra. Mat.-Fyz. Časopis Sloven. Akad. Vied 5 (1955), 101–113. (Slovak) MR 0074837
[18] A. Kotzig: On the theory of Euler polyhedra. Mat.-Fyz. Časopis Sloven. Akad. Vied 13 (1963), 20–31. (Russian) MR 0162176
[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 0001903 | Zbl 0024.28701
[21] O. Ore: The Four-Color Problem. Academic Press, New York, 1967. MR 0216979 | Zbl 0149.21101
[22] J. Zaks: Extending Kotzig’s theorem. Israel J. Math. 45 (1983), 281–296. DOI 10.1007/BF02804013 | MR 0720304 | Zbl 0524.05031
Search
Partner of
