A Steinberg-Like Approach to Describing Faces in 3-Polytopes

详细信息    查看全文

• 作者：O. V. Borodin ; A. O. Ivanova ; E. I. Vasil’eva
• 关键词：Plane map ; Plane graph ; 3 ; Polytope ; Structural properties ; Minor face ; Face type
• 刊名：Graphs and Combinatorics
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：33
• 期：1
• 页码：63-71
• 全文大小：en>
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Engineering Design;
• 出版者：Springer Japan
• ISSN：1435-5914
• 卷排序：33

文摘

It is trivial that every 3-polytope has a face of degree at most 5, called minor. Back in 1940, Lebesgue gave an approximate description of minor faces in 3-polytopes. Borodin (Diskretn Anal Issled Oper 9(3), 29–35, 2002) improved Lebesgue’s description on six parameters and suggested to find a tight description of minor faces. By now, such a tight description has been obtained only for several restricted classes of 3-polytopes. In 1976, Steinberg conjectured that every planar graph without 4-cycles and without 5-cycles is 3-colorable. Since 1993, a lot of research has been devoted to coloring sparse plane graphs, defined in terms of forbidding certain sets of cycle-lengths. One of the purposes of our paper is to suggest a similar approach to finding a tight version of Lebesgue’s description of minor faces; namely, by forbidding certain sets of vertex degrees. More specifically, a face is of type \((k_1,k_2,\ldots )\) if the set of degrees of its incident vertices is majorized by the vector \((k_1,k_2, \ldots )\). It follows from results by Horňák and Jendrol’ (Discus Math Graph Theory 16(2), 123–142, 1996) that every 3-polytope without vertices of degree from 4 to 7 has a face of one of the types \((3,3,\infty )\), (3, 8, 15), (3, 9, 14), (3, 10, 13), \((3,3,3,\infty )\), and (3, 3, 3, 3, 3). The other purpose of our paper is to obtain a description “eEquation" id="IEq5">\((3,3,\infty )\), (3, 8, 14), (3, 10, 12), \((3,3,3,\infty )\), (3, 3, 3, 3, 3)”, where all parameters are best possible.