LAUSR

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 )$$(k1,k2,…) if the set of degrees of its incident vertices is majorized by the vector $$(k_1,k_2, \ldots )$$(k1,k2,…). 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,3,∞), (3, 8, 15), (3, 9, 14), (3, 10, 13), $$(3,3,3,\infty )$$(3,3,3,∞), and (3, 3, 3, 3, 3). The other purpose of our paper is to obtain a description “$$(3,3,\infty )$$(3,3,∞), (3, 8, 14), (3, 10, 12), $$(3,3,3,\infty )$$(3,3,3,∞), (3, 3, 3, 3, 3)”, where all parameters are best possible.