Geodesic
More About the Height of Faces in 3-Polytopes
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 443-453.

Voir la notice de l'article provenant de la source Library of Science

The height of a face in a 3-polytope is the maximum degree of its incident vertices, and the height of a 3-polytope, h, is the minimum height of its faces. A face is pyramidal if it is either a 4-face incident with three 3-vertices, or a 3-face incident with two vertices of degree at most 4. If pyramidal faces are allowed, then h can be arbitrarily large, so we assume the absence of pyramidal faces in what follows. In 1940, Lebesgue proved that every quadrangulated 3-polytope has h ≤ 11. In 1995, this bound was lowered by Avgustinovich and Borodin to 10. Recently, Borodin and Ivanova improved it to the sharp bound 8. For plane triangulation without 4-vertices, Borodin (1992), confirming the Kotzig conjecture of 1979, proved that h ≤ 20, which bound is sharp. Later, Borodin (1998) proved that h ≤ 20 for all triangulated 3-polytopes. In 1996, Horňák and Jendrol’ proved for arbitrarily polytopes that h ≤ 23. Recently, Borodin and Ivanova obtained the sharp bounds 10 for trianglefree polytopes and 20 for arbitrary polytopes. In this paper we prove that any polytope has a face of degree at most 10 with height at most 20, where 10 and 20 are sharp.
Keywords: plane map, planar graph, 3-polytope, structural properties, height of face 
@article{DMGT_2018_38_2_a7,
     author = {Borodin, Oleg V. and Bykov, Mikhail A. and Ivanova, Anna O.},
     title = {More {About} the {Height} of {Faces} in {3-Polytopes}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {443--453},
     publisher = {mathdoc},
     volume = {38},
     number = {2},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a7/}
}
TY  - JOUR
AU  - Borodin, Oleg V.
AU  - Bykov, Mikhail A.
AU  - Ivanova, Anna O.
TI  - More About the Height of Faces in 3-Polytopes
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 443
EP  - 453
VL  - 38
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a7/
LA  - en
ID  - DMGT_2018_38_2_a7
ER  - 
%0 Journal Article
%A Borodin, Oleg V.
%A Bykov, Mikhail A.
%A Ivanova, Anna O.
%T More About the Height of Faces in 3-Polytopes
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 443-453
%V 38
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a7/
%G en
%F DMGT_2018_38_2_a7
Borodin, Oleg V.; Bykov, Mikhail A.; Ivanova, Anna O. More About the Height of Faces in 3-Polytopes. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 443-453. http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a7/

[1] S.V. Avgustinovich and O.V.Borodin, Neighborhoods of edges in normal maps, Diskretn. Anal. Issled. Oper. 2 (1995) 3–9, in Russian, translation in Ser. Mathematics and Its Applications 391 (1997) 17–22.

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

[3] O.V. Borodin, Solving the Kotzig and Grünbaum problems on the separability of a cycle in planar graphs, Mat. Zametki 46 (1989) 9–12, in Russian, translation in Math. Notes 46 (1992) 835–837.

[4] O.V. Borodin, Colorings of plane graphs: a survey, Discrete Math. 313 (2013) 517–539. doi:10.1016/j.disc.2012.11.011

[5] O.V. Borodin, Minimal weight of a face in planar triangulations without 4- vertices, Mat. Zametki 51 (1992) 16–19, in Russian, translation in Math. Notes 51 (1992) 11–13.

[6] O.V. Borodin, Triangulated 3- polytopes with restricted minimal weight of faces, Discrete Math. 186 (1998) 281–285. doi:10.1016/S0012-365X(97)00240-9

[7] O.V. Borodin, Strengthening Lebesgue’s theorem on the structure of the minor faces in convex polyhedra, Diskretn. Anal. Issled. Oper., Ser. 1 9 (2002) 29–39, in Russian.

[8] O.V. Borodin and D.V. Loparev, The height of minor faces in normal plane maps, Diskretn. Anal. Issled. Oper. 5 (1998) 6–17, translation in Discrete Appl. Math. 135 (2004) 31–39. doi:10.1016/S0166-218X(02)00292-5

[9] O.V. Borodin and A.O. Ivanova, Describing 3- faces in normal plane maps with minimum degree 4, Discrete Math. 313 (2013) 2841–2847. doi:10.1016/j.disc.2013.08.028

[10] O.V. Borodin and A.O. Ivanova, The vertex-face weight of edges in 3- polytopes, Sibirsk. Mat. Zh. 56 (2015) 338–350, in Russian, translation in Sib. Math. J. 56 (2015) 275–284. doi:10.1134/s003744661502007x

[11] O.V. Borodin and A.O. Ivanova, Heights of minor faces in triangle-free 3- polytopes, Sibirsk. Mat. Zh. 56 (2015) 982–988, in Russian, translation in Sib. Math. J. 56 (2015) 783–788. doi:10.1134/S003744661505002X

[12] O.V. Borodin and A.O. Ivanova, The weight of faces in normal plane maps, Discrete Math. 339 (2016) 2573–2580. doi:10.1016/j.disc.2016.04.018

[13] O.V. Borodin and A.O. Ivanova, Heights of faces in 3- polytopes, Sibirsk. Mat. Zh. 58 (2017) 48–55, in Russian, translation in Sib. Math. J. 58 (2017) 37–42. doi:10.1134/S0037446617010050

[14] O.V. Borodin and A.O. Ivanova, Low minor faces in 3- polytopes, Discrete Math., accepted.

[15] O.V. Borodin, A.O. Ivanova and A.V. Kostochka, Describing faces in plane triangulations, Discrete Math. 319 (2014) 47–61. doi:10.1016/j.disc.2013.11.021

[16] O.V. Borodin and D.R. Woodall, The weight of faces in plane maps, Mat. Zametki 64 (1998) 648–657, in Russian. doi:10.4213/mzm1441

[17] O.V. Borodin and D.R. Woodall, Cyclic degrees of 3- polytopes, Graphs Combin. 15 (1999) 267–277. doi:10.1007/S003730050060

[18] B. Ferencová and T. Madaras, Light graphs in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight, Discrete Math. 310 (2010) 1661–1675.

[19] B. Grünbaum, Polytopal graphs, in: Studies in Graph Theory, D.R. Fulkerson, Ed., MAA Studies in Mathematics 12 (1975) 201–224.

[20] M. Horňák and S. Jendrol’, Unavoidable sets of face types for planar maps, Discuss. Math. Graph Theory 16 (1996) 123–142. doi:10.7151/dmgt.1028

[21] S. Jendrol’, Triangles with restricted degrees of their boundary vertices in plane triangulations, Discrete Math. 196 (1999) 177–196. doi:10.1016/S0012-365X(98)00172-1

[22] S. Jendrol’ and H.-J. Voss, Light subgraphs of graphs embedded in the plane—a survey, Discrete Math. 313 (2013) 406–421. doi:10.1016/j.disc.2012.11.007

[23] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat. Eas. SAV (Math. Slovaca) 5 (1955) 101–113.

[24] A. Kotzig, From the theory of Eulerian polyhedrons, Mat. Eas. SAV (Math. Slovaca) 13 (1963) 20–34.

[25] A. Kotzig, Extremal polyhedral graphs, Ann. New York Acad. Sci. 319 (1979) 569–570. doi:10.1111/j.1749-6632.1979.tb32837.x

[26] H. Lebesgue, Quelques conséquences simples de la formule d’Euler, J. Math. Pures Appl. 19 (1940) 27–43.

[27] B.Mohar, R. & Skrekovski and H.-J. Voss, Light subraphs in planar graphs of minimum degree 4 and edge-degree 9, J. Graph Theory 44 (2003) 261–295. doi:10.1002/jgt.10144

[28] O. Ore and M.D. Plummer, Cyclic coloration of plane graphs, in: Recent Progress in Combinatorics, W.T. Tutte (Ed.), (Academic Press, New York, 1969) 287–293.

[29] M.D. Plummer, On the cyclic connectivity of planar graph, Graph Theory and Application (Springer, Berlin, 1972) 235–242.

[30] E. Steinitz, Polyeder und Raumeinteilungen, Enzykl. Math. Wiss. (Geometrie), 3AB 12 (1922) 1–139.

[31] P. Wernicke, Über den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413–426. doi:10.1007/BF01444968