Authors:
O.V. Borodin, M.A. Bykov, A.O. Ivanova
Title:
More about the height of faces in 3-polytopes
Source:
Discussiones Mathematicae Graph Theory
Received 24.05.2016, Revised 12.12.2016, Accepted 12.12.2016, doi: 10.7151/dmgt.2014

Abstract:
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\le11. 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\le20, which bound is sharp. Later, Borodin (1998) proved that h\le20 for all triangulated 3-polytopes. In 1996, Hor\v{n}ák and Jendrol' proved for arbitrarily polytopes that h\le23. Recently, Borodin and Ivanova obtained the sharp bounds 10 for triangle-free 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

Links:
PDF