×

zbMATH — the first resource for mathematics

Describing short paths in plane graphs of girth at least 5. (English) Zbl 1302.05040
Summary: We prove that every connected plane graph of given girth \(g\) and minimum degree at least 2 contains an edge whose degrees are bounded from above by one of the pairs \((2, 5)\) or \((3, 3)\) if \(g = 5\), by pair \((2, 5)\) if \(g = 6\), by pair \((2, 3)\) if \(g \in \{7, 8, 9, 10 \}\), and by pair \((2, 2)\) if \(g \geq 11\). Further we prove that every connected plane graph of given girth \(g\) and minimum degree at least 2 has a path on three vertices whose degrees are bounded from above by one of the triplets \((2, \infty, 2)\), \((2, 2, 6)\), \((2, 3, 5)\), \((2, 4, 4)\), or \((3, 3, 3)\) if \(g = 5\), by one of the triplets \((2, 2, \infty)\), \((2, 3, 5)\), \((2, 4, 3)\), or \((2, 5, 2)\) if \(g = 6\), by one of the triplets \((2, 2, 6)\), \((2, 3, 3)\), or \((2, 4, 2)\) if \(g = 7\), by one of the triplets \((2, 2, 5)\) or \((2, 3, 3)\) if \(g \in \{8, 9 \}\), by one of the triplets \((2, 2, 3)\) or \((2, 3, 2)\) if \(g \geq 10\), and by the triplet \((2, 2, 2)\) if \(g \geq 16\).

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
05C07 Vertex degrees
05C35 Extremal problems in graph theory
05C22 Signed and weighted graphs
05C40 Connectivity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] K. Ando, S. Iwasaki, A. Kaneko, Every 3-connected planar graph has a connected subgraph with small degree sum in: Annual Meeting of Mathematical Society of Japan, 1993 (in Japanese).
[2] Bondy, J. A.; Murty, U. S.R., Graph theory, (2008), Springer · Zbl 1134.05001
[3] Borodin, O. V., On the total coloring of planar graphs, J. Reine Angew. Math., 394, 180-185, (1989) · Zbl 0653.05029
[4] Borodin, O. V.; Ivanova, A. O.; Jensen, T. R.; Kostochka, A. V.; Yancey, M., Describing 3-paths in normal plane maps, Discrete Math., 313, 2702-2711, (2013) · Zbl 1280.05026
[5] D.W. Cranston, D.B. West, A guide to Discharging method, arXiv:1306.4434 [math.CO] 19 Jun 2013.
[6] Franklin, Ph., The four-color problem, Amer. J. Math., 44, 225-236, (1922) · JFM 48.0664.02
[7] B. Grünbaum, New views on some old questions of combinatorial geometry, in: Int. Teorie Combinatorie, Rome, (1992), Vol. 1, 1976, pp. 451-468.
[8] Jendrol’, S., A structural property of convex 3-polytopes, Geom. Dedicata, 68, 91-99, (1997) · Zbl 0893.52007
[9] Jendrol’, S.; Voss, H.-J., Light subgraphs of graphs embedded in the plane — a survey, Discrete Math., 313, 406-421, (2013) · Zbl 1259.05045
[10] Kotzig, A., Contribution to the theory of Eulerian polyhedra, Mat. Čas., 5, 101-113, (1955), (in Slovak)
[11] Lebesgue, H., Quelques conséquences simples de la formule d’euler, J. Math. Pures Appl., 19, 27-43, (1940) · JFM 66.0736.03
[12] Wernicke, P., Über den kartographischen vierfarbensatz, Math. Ann., 58, 413-426, (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.