zbMATH — the first resource for mathematics

On light edges and triangles in planar graphs of minimum degree five. (English) Zbl 0813.05020
Let \(G\) be a planar graph of minimum degree five. Denote by \(e_{i,j}\) the number of edges of \(G\) joining a vertex of degree \(i\) to a vertex of degree \(j\), and by \(f_{i,j,k}\) the number of faces of \(G\) which have exactly one vertex of degree \(i\), \(j\), and \(k\), respectively, in their boundary. The first result states that \(7e_{5,5}+ 3e_{5,6}\geq 180\), with the coefficients being best possible. Secondly, an example is provided to show that the coefficients in a previous inequality of Borodin, namely \[ 18 f_{5,5,5}+ 9 f_{5,5,6}+ 5 f_{5,5,7}+ 4f _{5,6,6}\geq 144, \] are best possible.

05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
PDF BibTeX Cite
Full Text: DOI
[1] Borodin, Solution of Problems of Kotzig and Grünbaum Concerning the Isolation of Cycles in Planar Graphs, Math. Notes 46 pp 835– (1989) · Zbl 0717.05034
[2] Borodin, Structural Properties of Planar Maps with the Minimal Degree 5, Math. Nachr. 158 pp 109– (1992) · Zbl 0776.05035
[3] Grünbaum, Acyclic Colorings of Planar Graphs, Israel J. Math. 14 pp 390– (1973) · Zbl 0265.05103
[4] Grünbaum, Polytopal Graphs, MAA Stud. Math. 12 pp 201– (1975)
[5] Grünbaum, Analogues for Tilings of Kotzig’s Theorem on Minimal Weights of Edges, Ann. Discrete Math. 12 pp 129– (1982) · Zbl 0504.05026
[6] Kotzig, From the Theory of Euler’s Polyhedrons, Mat. Čas. 13 pp 20– (1963) · Zbl 0134.19601
[7] Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 pp 413– (1904) · JFM 35.0511.01
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.