zbMATH — the first resource for mathematics

Subgraphs with restricted degrees of their vertices in planar 3-connected graphs. (English) Zbl 0891.05025
Every 3-connected planar graph \(G\) either contains a path with \(k\) vertices each of degree at most \(5k\) or does not contain any path with \(k\) vertices; the bound \(5k\) is the best possible. Moreover, for every connected planar graph \(H\) other than a path and for every integer \(m\geq 3\) there is a 3-connected planar graph \(G\) such that each copy of \(H\) in \(G\) contains a vertex of degree at least \(m\).

05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
Full Text: DOI
[1] Bondy, J.A., Murty, U.S.R.: Graph theory with applications. Amsterdam: North- Holland 1976 · Zbl 1226.05083
[2] Borodin, OV, On the total coloring of planar graphs, J. Reine Ange. Math, 394, 180-185, (1989) · Zbl 0653.05029
[3] Borodin, OV, Precise lower bound for the number of edges of minor weight in planar maps, Math. Slovaca, 42, 129-142, (1992) · Zbl 0767.05039
[4] GrÜnbaum, B, New views on some old questions of combinatorial geometry, in theorie combinatorie, proc. int. colloquium, Rome, 1973, Accademia nay. dei. lincei Rome, 1, 451-468, (1976)
[5] GrÜnbaum, B.: Polytopal graphs, in Studies in Graph Theory (D.R. Fulkerson, ed.), MAA Studies in Mathematics 12, 201-224 (1975) · Zbl 0653.05029
[6] GrÜnbaum, B; Shephard, GC, Analogues for tiling of kotzig’s theorem on minimal weights of edges, Ann. Discrete Math, 12, 129-140, (1982) · Zbl 0504.05026
[7] Ivanco, J, The weight of a graph, Ann. Discrete Math, 51, 113-116, (1992) · Zbl 0773.05066
[8] Jendrol’, S.: Path with restricted degrees of their vertices in planar graphs. Czechoslovak Math. J. (to appear) · Zbl 1003.05055
[9] Jendrol’, S.: A structural property of 3-connected planar graphs, (submitted) · Zbl 0893.52007
[10] Jucoviǒ, E, Strengthening of a theorem about 3-polytopes, Geometria Dedicata, 3, 233-237, (1973) · Zbl 0297.52006
[11] Kotzig, A, Contribution to the theory of Eulerian polyhedra, Math. Čas. SAV (Math. Slovaca), 5, 111-113, (1955)
[12] Kotzig, A, Extremal polyhedral graphs, Ann. New York Acad. Sci, 319, 569-570, (1979)
[13] Zaks, J, Extending kotzig’s theorem, Israel J. Math, 45, 281-296, (1983) · 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.