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