Another tight description of faces in plane triangulations with minimum degree 4 Full article
| Journal |
Discrete Mathematics
ISSN: 0012-365X , E-ISSN: 1872-681X |
||||
|---|---|---|---|---|---|
| Output data | Year: 2022, Volume: 345, Number: 9, Article number : 112964, Pages count : 10 DOI: 10.1016/j.disc.2022.112964 | ||||
| Tags | 3-polytope; Lebesgue's theorem; Planar graph; Plane triangulation; Structure properties; Weight | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (2)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0017 |
| 2 | Министерство науки и высшего образования РФ | FSRG-2020-0006 |
Abstract:
It follows from the classical theorem by Lebesgue (1940) on the structure of minor faces in 3-polytopes that every plane triangulation with minimum degree at least 4 has a 3-face for which the set of degrees of its vertices is majorized by one of the following sequences: (4,4,∞), (4,5,19), (4,6,11), (4,7,9), (5,5,9), (5,6,7). In 1999, Jendrol' gave the following description of faces: (4,4,∞), (4,5,13), (4,6,17), (4,7,8), (5,5,7), (5,6,6). Also, Jendrol' (1999) conjectured that there is a face of one of the types: (4,4,∞), (4,5,10), (4,6,15), (4,7,7), (5,5,7), (5,6,6). In 2002, Lebesgue's description was strengthened by Borodin to (4,4,∞), (4,5,17), (4,6,11), (4,7,8), (5,5,8), (5,6,6). In 2014, we obtained the following tight description, which, in particular, disproves the above mentioned conjecture by Jendrol': (4,4,∞), (4,5,11), (4,6,10), (4,7,7), (5,5,7), (5,6,6). The purpose of this paper is to give another tight description of faces in plane triangulations with minimum degree at least 4: (4,4,∞), (4,6,10), (4,7,7), (5,5,8), (5,6,7).
Cite:
Borodin O.V.
, Ivanova A.O.
Another tight description of faces in plane triangulations with minimum degree 4
Discrete Mathematics. 2022. V.345. N9. 112964 :1-10. DOI: 10.1016/j.disc.2022.112964 WOS Scopus РИНЦ OpenAlex
Another tight description of faces in plane triangulations with minimum degree 4
Discrete Mathematics. 2022. V.345. N9. 112964 :1-10. DOI: 10.1016/j.disc.2022.112964 WOS Scopus РИНЦ OpenAlex
Dates:
| Submitted: | Oct 18, 2021 |
| Accepted: | Apr 24, 2022 |
| Published online: | May 9, 2022 |
Identifiers:
| Web of science: | WOS:000806503700006 |
| Scopus: | 2-s2.0-85129486515 |
| Elibrary: | 48589095 |
| OpenAlex: | W4229367144 |