Triangles with restricted degree sum of their boundary vertices in plane graphs.

*(English)*Zbl 0814.05030From the author’s abstract: It is known that under appropriate assumptions, each plane graph contains a vertex of degree at most 5 and a pair of adjacent vertices with degree sum at most 13. Two structural assumptions are established for a plane graph which together guarantee the existence of a triple of pairwise adjacent vertices with restricted degree sum. As shown by constructions, if any of these assumptions is violated, the degree sum of each three pairwise adjacent vertices may be arbitrarily large. As for a quadruple of pairwise adjacent vertices, it can hardly be forced in a plane graph by means of any reasonable restrictions.

Reviewer: M.Marx (Pensacola)

##### MSC:

05C10 | Planar graphs; geometric and topological aspects of graph theory |

PDF
BibTeX
XML
Cite

\textit{O. V. Borodin}, Discrete Math. 137, No. 1--3, 45--51 (1995; Zbl 0814.05030)

Full Text:
DOI

##### References:

[1] | Borodin, O.V., Solution of Kotzig’s and grünbaum’s problems on separability of a cycle in planar graphs, Mat. zametki, 46, 9-12, (1989), (in Russian) · Zbl 0694.05027 |

[2] | Borodin, O.V., On the total coloring of planar graphs, J. reine angew. math., 394, 180-185, (1989) · Zbl 0653.05029 |

[3] | Borodin, O.V., Minimum face weight in plane triangulations without 4-vertices, Mat. zametki, 51, 16-19, (1992), (in Russian) · Zbl 0755.05091 |

[4] | Grünbaum, B., New views on some old questions of combinatorial geometry, (), 451-468 |

[5] | Grünbaum, B., Polytopal graphs, Math. assoc. America studies math., 12, 201-224, (1975) · Zbl 0323.05104 |

[6] | Kotzig, A., Contribution to the theory of Eulerian polyhedra, Mat. cas., 5, 101-103, (1955) |

[7] | Kotzig, A., From the theory of Euler’s polyhedrons, Mat. čas., 13, 20-34, (1963) · Zbl 0134.19601 |

[8] | Kotzig, A., Extremal polyhedral graphs, (), 569-570 |

[9] | Plummer, M.D., On the cyclic connectivity of planar graphs, (), 235-242 · Zbl 0247.05113 |

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.