RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2024 Volume 65, Number 2, Pages 249–257 (Mi smj7852)

Light $3$-paths in $3$-polytopes without adjacent triangles

O. V. Borodina, A. O. Ivanovab

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
b North-Eastern Federal University named after M. K. Ammosov, Yakutsk

Abstract: Let $w_k$ be the maximum of the minimum degree-sum (weight) of vertices in $k$-vertex paths ($k$-paths) in $3$-polytopes. Trivially, each $3$-polytope has a vertex of degree at most $5$, and so $w_1\le5$. Back in $1955$, Kotzig proved that $w_2\le13$ (so there is an edge of weight at most $13$), which is sharp. In $1993$, Ando, Iwasaki, and Kaneko proved that $w_3\le21$, which is also sharp due to a construction by Jendrol' of $1997$. In $1997$, Borodin refined this by proving that $w_3\le18$ for 3-polytopes with $w_2\ge7$, while $w_3\le17$ holds for $3$-polytopes with $w_2\ge8$, where the sharpness of 18 was confirmed by Borodin et al. in $2013$, and that of $17$ was known long ago. Over the last three decades, much research has been devoted to structural and coloring problems on the plane graphs that are sparse in this or that sense. In this paper we deal with $3$-polytopes without adjacent $3$-cycles that is without chordal $4$-cycle (in other words, without $K_4-e$). It is known that such $3$-polytopes satisfy $w_1\le4$; and, moreover, $w_2\le9$ holds, where both bounds are sharp (Borodin, $1992$). We prove now that each $3$-polytope without chordal $4$-cycles has a $3$-path of weight at most $15$; and so $w_3\le15$, which is sharp.

Keywords: plane graph, $3$-polytope, sparse polytope, structural property, $3$-path, weight.

UDC: 519.17

MSC: 35R30

Received: 17.10.2023
Accepted: 28.11.2023

DOI: 10.33048/smzh.2024.65.202



© Steklov Math. Inst. of RAS, 2024