Describing Minor 5-Stars in 3-Polytopes with Minimum Degree 5 and No Vertices of Degree 6 or 7

Batueva, Ts.Ch-D.; Borodin, O.V.; Ivanova, A.O.; Nikiforov, D.V.

Geodesic

Parcourir par

Describing Minor 5-Stars in 3-Polytopes with Minimum Degree 5 and No Vertices of Degree 6 or 7

Batueva, Ts.Ch-D. ; Borodin, O.V. ; Ivanova, A.O. ; Nikiforov, D.V.

Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 535-548

Voir la notice de l'article provenant de la source Library of Science

Résumé

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 P₅ of 3-polytopes with minimum degree 5. This description depends on 32 main parameters. (6, 6, 7, 7, 7), (6, 6, 6, 7, 9), (6, 6, 6, 6, 11), (5, 6, 7, 7, 8), (5, 6, 6, 7, 12), (5, 6, 6, 8, 10), (5, 6, 6, 6, 17), (5, 5, 7, 7, 13), (5, 5, 7, 8, 10), (5, 5, 6, 7, 27), (5, 5, 6, 6, ∞), (5, 5, 6, 8, 15), (5, 5, 6, 9, 11), (5, 5, 5, 7, 41), (5, 5, 5, 8, 23), (5, 5, 5, 9, 17), (5, 5, 5, 10, 14), (5, 5, 5, 11, 13) Not many precise upper bounds on these parameters have been obtained as yet, even for restricted subclasses in P₅. In 2018, Borodin, Ivanova, Kazak proved that every forbidding vertices of degree from 7 to 11 results in a tight description (5, 5, 6, 6, ∞), (5, 6, 6, 6, 15), (6, 6, 6, 6, 6). Recently, Borodin, Ivanova, and Kazak proved every 3-polytope in P₅ with no vertices of degrees 6, 7, and 8 has a 5-vertex whose neighborhood is majorized by one of the sequences (5, 5, 5, 5, ∞) and (5, 5, 10, 5, 12), which is tight and improves a corresponding description (5, 5, 5, 5, ∞), (5, 5, 9, 5, 17), (5, 5, 10, 5, 14), (5, 5, 11, 5, 13) that follows from the Lebesgue Theorem. The purpose of this paper is to prove that every 3-polytope with minimum degree 5 and no vertices of degree 6 or 7 has a 5-vertex whose neighborhood is majorized by one of the ordered sequences (5, 5, 5, 5, ∞), (5, 5, 8, 5, 14), or (5, 5, 10, 5, 12).

Keywords: planar graph, structural properties, 3-polytope, 5-star, neighborhood

@article{DMGT_2022_42_2_a11,
     author = {Batueva, Ts.Ch-D. and Borodin, O.V. and Ivanova, A.O. and Nikiforov, D.V.},
     title = {Describing {Minor} {5-Stars} in {3-Polytopes} with {Minimum} {Degree} 5 and {No} {Vertices} of {Degree} 6 or 7},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {535--548},
     publisher = {mathdoc},
     volume = {42},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a11/}
}

TY  - JOUR
AU  - Batueva, Ts.Ch-D.
AU  - Borodin, O.V.
AU  - Ivanova, A.O.
AU  - Nikiforov, D.V.
TI  - Describing Minor 5-Stars in 3-Polytopes with Minimum Degree 5 and No Vertices of Degree 6 or 7
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 535
EP  - 548
VL  - 42
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a11/
LA  - en
ID  - DMGT_2022_42_2_a11
ER  -

%0 Journal Article
%A Batueva, Ts.Ch-D.
%A Borodin, O.V.
%A Ivanova, A.O.
%A Nikiforov, D.V.
%T Describing Minor 5-Stars in 3-Polytopes with Minimum Degree 5 and No Vertices of Degree 6 or 7
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 535-548
%V 42
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a11/
%G en
%F DMGT_2022_42_2_a11

Batueva, Ts.Ch-D.; Borodin, O.V.; Ivanova, A.O.; Nikiforov, D.V. Describing Minor 5-Stars in 3-Polytopes with Minimum Degree 5 and No Vertices of Degree 6 or 7. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 535-548. http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a11/