Search

In 1940, in attempts to solve the Four Color Problem, Henry Lebesgue gave an approximate description of the neighborhoods of 5-vertices in the class P5 of 3-polytopes with minimum degree 5. This description depends on 32 main parameters.

Abstract A description of paths on three vertices (3-paths) in normal plane maps (NPMs) is tight if no parameter of this description can be improved and no term dropped. We know that there are precisely seven tight descriptions of 3-paths in triangle-free NPMs: { (5 , 3 , 6) , (4 , 3 , 7) } , { (3 , 5 , 3) , (3 , 4 , 4) } , { (5 , 3 , 6) , (3 , 4 , 3) } , { (3 , 5 , 3) , (4 , 3 , 4) } , (5 , 3 , 7) , (3 , 5 , 4) , and (5 , 4 , 6). The problem of describing all tight descriptions of 3-paths in arbitrary NPMs is widely open. It is only known that there are precisely three tight descriptions consisting of one triplet of restrictions on the vertex degrees of 3-paths: (5 , ∞ , 6) , (5 , 10 , ∞) , or (10 , 5 , ∞). If NPMs are allowed to have K 4 − e as subgraphs, then it can happen that every 3-path goes through a vertex of unbounded degree: for example, we delete every other horizontal edge from a double 2 n -pyramid. This fact explains the appearance of ∞ in the above description. The purpose of this paper is to prove that there are precisely four tight one-term descriptions of 3-paths in normal plane maps without K 4 − e : (10 , 5 , 20) , (10 , 6 , 15) , (5 , 10 , 15) , and (5 , 15 , 6). In particular, the same description holds for 3-polytopes. [ABSTRACT FROM AUTHOR]

Let w Δ be the minimum integer W with the property that every 3-polytope with minimum degree 5 and maximum degree Δ has a vertex of degree 5 with the degree-sum (weight) of all vertices in its closed neighborhood at most W . Trivially, w 5 = 30 and w 6 = 35 . In 1940, Lebesgue proved w Δ ≤ Δ + 31 for all Δ ≥ 5 and w Δ ≤ Δ + 27 for Δ ≥ 41 . In 1998, the first Lebesgue’s result was improved by Borodin and Woodall to w Δ ≤ Δ + 30 . This bound is sharp for Δ = 7 due to Borodin (1992) and Jendrol’ and Madaras (1996), Δ = 9 due to Borodin and Ivanova (2013), Δ = 10 due to Jendrol’ and Madaras (1996), and Δ = 12 due to Borodin and Woodall (1998). As for the second Lebesgue’s bound, Borodin et al. (2014) proved that w Δ ≤ Δ + 27 for Δ ≥ 28 , but w 20 ≥ 48 ; the former fact was extended by Borodin and Ivanova (2016) to w Δ ≤ Δ + 27 for Δ ≥ 23 . The purpose of this paper is to prove w Δ ≤ Δ + 29 whenever Δ ≥ 13 and show that w 8 = 38 , w 11 = 41 , and w 13 = 42 . Thus w Δ remains unknown only for 14 ≤ Δ ≤ 22 . [ABSTRACT FROM AUTHOR]