Every triangulated 3-polytope of minimum degree 4 has a 4-path of weight at most 27 (Q727044): Difference between revisions

Summary: By \(\delta\) and \(w_k\) denote the minimum degree and minimum degree-sum (weight) of a \(k\)-vertex path in a given graph, respectively. For every 3-polytope, \(w_2\leq 13\) and \(w_3\leq 21\), where both bounds are sharp. For every 3-polytope with \(\delta\geq 4\), we have sharp bounds \(w_2\leq 11\) and \(w_3\leq 17\). { }\textit{T. Madaras} [Discuss. Math., Graph Theory 24, No. 3, 403--411 (2004; Zbl 1063.05038)] proved that every triangulated 3-polytope with \(\delta\geq 4\) satisfies \(w_4\leq 31\) and constructed such a 3-polytope with \(w_4=27\).{ }We improve the Madaras bound \(w_4\leq 31\) to the sharp bound \(w_4\leq 27\).