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

Sibirsk. Mat. Zh., 2021 Volume 62, Number 3, Pages 498–508 (Mi smj7571)

A tight description of $3$-polytopes by their major $3$-paths

O. V. Borodin, A. O. Ivanova

Sobolev Institute of Mathematics, Novosibirsk, Russia

Abstract: A $3$-path $uvw$ in a $3$-polytope is an $(i,j,k)$-path if $d(u)\le i$, $d(v)\le j$, and $d(w)\le k$, where $d(x)$ is the degree of a vertex $x$. It is well known that each $3$-polytope has a vertex of degree at most $5$ called minor. A description of $3$-paths in a $3$-polytope is minor or major if the central item of its every triplet is at least $6$. Back in 1922, Franklin proved that each $3$-polytope with minimum degree $5$ has a $(6,5,6)$-path which description is tight. In 2016, we proved that each polytope with minimum degree $5$ has a $(5,6,6)$-path which is also tight. For arbitrary $3$-polytopes, Jendrol' (1996) gave the following description of $3$-paths:
$$ \{(10,3,10), (7,4,7),(6,5,6),(3,4,15),(3,6,11),(3,8,5),(3,10,3),(4,4,11),(4,5,7),(4,7,5)\}, $$
but it is unknown whether the description is tight or not. The first tight description of $3$-paths was obtained in 2013 by Borodin et al.:
$$ \{(3,4,11), (3,7,5), (3,10,4), (3,15,3), (4,4,9), (6,4,8), (7,4,7), (6,5,6)\}. $$
Another tight description was given by Borodin, Ivanova, and Kostochka in 2017:
$$ \{(3,15,3), (3,10,4), (3,8,5), (4,7,4), (5,5,7), (6,5,6), (3,4,11), (4,4,9), (6,4,7)\}. $$
The purpose of this paper is to obtain the following major tight descriptions of $3$-paths for arbitrary $3$-polytopes:
$$ \{(3,18,3),(3,11,4),(3,8,5),(3,7,6),(4,9,4),(4,7,5),(5,6,6)\}. $$


Keywords: plane graph, $3$-polytope, structural properties, $3$-path, tight description.

UDC: 519.17

Received: 29.09.2020
Revised: 21.01.2021
Accepted: 22.01.2021

DOI: 10.33048/smzh.2021.62.302


 English version:
Siberian Mathematical Journal, 2021, 62:3, 400–408

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025