Describing edges incident with minor faces in 3-polytopes without adjacent 3-faces

The weight w(e) of an edge e in a 3-polytope is the degree-sum of its endvertices. An edge e = uv is an (i, j)-edge if d(u) ≤ i and d(v) ≤ j. In 1940 Lebesgue proved that every 3-polytope has a (3, 11)-edge, or (4, 7)-edge, or (5, 6)-edge, where 7 and 6 are best possible. In 1955, Kotzig proved that every 3-polytope has an edge e with w(e) ≤ 13, which bound is sharp. Borodin (1987), answering Erd˝os’ question of 1976, proved that every plane graph without vertices of degree less than 3 has such an edge. Moreover, Borodin (1991) refined this by proving that there is either a (3, 10)-edge, or (4, 7)-edge, or (5, 6)-edge.

Given a 3-polytope, the minimum weight of all its edges is denoted by w, of those incident with just one 3-face and called semi-weak is w∗, and those incident with two 3-faces and called weak, is w∗∗. Borodin (1996) proved that if w∗∗ = ∞, that is there are no weak edges, then either w∗ ≤ 9 or w ≤ 8, where both bounds are sharp.

Recently, we refined this fact by proving that w∗∗ = ∞ implies either a semi-weak (3, 6)-edge, or semi-weak (4, 4)-edge, or else a strong (3, 5)-edge, which description is tight. (Note that if (3, 5)-edges are allowed, then there may be no 3-faces, and hence semi-weak edges, at all.)

The purpose of our note is to further refine these results by proving that in fact w∗∗ = ∞ implies either a semi-weak (3, 6)-edge, or semi-weak (4, 4)-edge, or a strong (3, 5)-edge incident with a 4-face, or else a strong (3, 3)-edge incident with a 5-face, where no parameter can be improved.

1. Wernicke P., “Uber den Kartographischen Vierfarbensatz,” Math. Ann., ¨ 58, 413–426 (1904).

2. Lebesgue H., “Quelques cons´equences simples de la formule d’Euler,” J. Math. Pures Appl., 19, 27–43 (1940).

3. Kotzig A., “Contribution to the theory of Eulerian polyhedra [in Slovak],” Mat. Cas., ˇ 5, 101– 103 (1940).

4. Gr¨unbaum B., “New views on some old questions of combinatorial geometry,” Int. Teorie Comb., Rome, 1, 451–468 (1976).

5. Borodin O. V., “Coupled colorings of graphs on a plane [in Russian],” Metody Diskret. Analiza, 45, 21–27 (1987).

6. Borodin O. V., “The structure of neighborhoods of an edge in planar graphs and the simultaneous coloring of vertices, edges and faces [in Russian],” Mat. Zametki, 53, No. 5, 35–47 (1993).

7. Borodin O. V., “Joint extension of two Kotzig’s theorems on 3-polytopes,” Combinatorica, 13, No. 1, 121–125 (1992).

8. Borodin O. V. and Ivanova A. O., “New results about the structure of plane graphs: a survey,” AIP Conf. Proc., 1907, 030051 (2017).

9. Jendrol’ S. and Voss H.-J., “Light subgraphs of graphs embedded in the plane: a survey,” Discrete Math., 313, No. 4, 406–421 (2013).

10. Aksenov V. A., Borodin O. V., and Ivanova A. O., “An extension of Kotzig’s theorem,” Discuss. Math. Graph Theory, 36, 889–897 (2016).

11. Batueva Ts. Ch-D., Borodin O. V., Bykov M. A., Ivanova A. O., Kazak O. N., and Nikiforov D. V., “Refined weight of edges in normal plane maps,” Discrete Math., 340, No. 11, 2659–2664 (2017).

12. Borodin O. V., “Joint generalization of the theorems of Lebesgue and Kotzig on the combinatorics of planar maps [in Russian],” Diskret. Mat., 3, No. 4, (1991) 24–27.

13. Borodin O. V., “Structural theorem on plane graphs with application to the entire coloring,” J. Graph Theory, 23, No. 3, 233–239 (1996).

14. Borodin O. V., “More about the weight of edges in planar graphs,” Tatra Mt. Math. Publ., 9, 11–14 (1996).

15. Borodin O. V. and Ivanova A. O., “Weight of edges in normal plane maps,” Discrete Math., 339, No. 5, 1507–1511 (2016).

16. Borodin O. V. and Ivanova A. O., “An improvement of Lebesgue’s description of edges in 3-polytopes and faces in plane quadrangulations,” Discrete Math., 342, No. 6, 1820–1827 (2019).

17. Borodin O. V. and Ivanova A. O., “Describing edges in normal plane maps having bo adjacent 3-faces,” Sib. Elektron. Math. Rep., 21, No. 1, 495–500 (2024).

18. Borodin O. V., Ivanova A. O., Kostochka A. V., and Sheikh N. N., “Minimax degrees of quasiplane graphs without 4-faces,” Sib. Elektron. Math. Rep., 4, 435–439 (2007).

19. Cekanov´a K., Macekov´a M., and Sotak R. ˇ , “Structure of edges in plane graphs with bounded dual edge weight,” Discrete Math., 344, No. 8, 112477 (2021).

20. Dvoˇr´ak Z. and Postle L., “Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8,” J. Comb. Theory Ser. B., 129, 38–54 (2018).

21. Ferencov´a B. and Madaras T., “On the structure of polyhedral graphs with prescribed edge and dual edge weight,” Acta Univ. M. Belii Math., 12, 13–18 (2005).

22. Ferencov´a B. and Madaras T., “Light graph in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight,” Discrete Math., 310, 1661–1675 (2010).

23. Hudak P., Macekov´a M., Madaras T., and P. Siroczki, “More on the structure of plane graphs with prescribed degrees of vertices, faces, edges and dual edges,” Ars Math. Contemp., 13, No. 2, 355–366 (2017).

24. Jendrol’ S. and Macekov´a M., “Describing short paths in plane graphs of girth at least 5,” Discrete Math., 338, 149–158 (2015).