Geodesic
Light neighborhoods of $5$-vertices in $3$-polytopes with minimum degree~$5$
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 13 (2016), pp. 584-591.

Voir la notice de l'article provenant de la source Math-Net.Ru

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 $\mathbf{P}_5$ of $3$-polytopes with minimum degree $5$. Given a $3$-polytope $P$, by $w(P)$ ($h(P)$) we denote the minimum degree-sum (minimum of the maximum degrees) of the neighborhoods of $5$-vertices in $P$. A $5^*$-vertex is a $5$-vertex adjacent to four $5$-vertices. It is known that if a polytope $P$ in $\mathbf{P}_5$ has a $5^*$-vertex, then $h(P)$ can be arbitrarily large. For each $P$ without vertices of degrees from $6$ to $9$ and $5^*$-vertices in $\mathbf{P}_5$, it follows from Lebesgue's Theorem that $w(P)\le 44$ and $h(P)\le 14$. In this paper, we prove that every such polytope $P$ satisfies $w(P)\le 42$ and $h(P)\le 12$, where both bounds are tight.
Keywords: planar map, planar graph, $3$-polytope, structural properties, height, weight. 
@article{SEMR_2016_13_a61,
     author = {O. V. Borodin and A. O. Ivanova},
     title = {Light neighborhoods of $5$-vertices in $3$-polytopes with minimum degree~$5$},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {584--591},
     publisher = {mathdoc},
     volume = {13},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2016_13_a61/}
}
TY  - JOUR
AU  - O. V. Borodin
AU  - A. O. Ivanova
TI  - Light neighborhoods of $5$-vertices in $3$-polytopes with minimum degree~$5$
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2016
SP  - 584
EP  - 591
VL  - 13
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2016_13_a61/
LA  - en
ID  - SEMR_2016_13_a61
ER  - 
%0 Journal Article
%A O. V. Borodin
%A A. O. Ivanova
%T Light neighborhoods of $5$-vertices in $3$-polytopes with minimum degree~$5$
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2016
%P 584-591
%V 13
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2016_13_a61/
%G en
%F SEMR_2016_13_a61
O. V. Borodin; A. O. Ivanova. Light neighborhoods of $5$-vertices in $3$-polytopes with minimum degree~$5$. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 13 (2016), pp. 584-591. http://geodesic.mathdoc.fr/item/SEMR_2016_13_a61/

[1] J. Balogh, M. Kochol, A. Pluhár, X. Yu, “Covering planar graphs with forests”, J. Combin. Theory Ser. B, 94 (2005), 147–158 | DOI | MR | Zbl

[2] O. V. Borodin, “Solution of Kotzig's and Grünbaum's problems on the separability of a cycle in a planar graph”, Matem. Zametki, 46:5 (1989), 9–12 (in Russian) | MR

[3] O. V. Borodin, D. R. Woodall, “Short cycles of low weight in normal plane maps with minimum degree $5$”, Discuss. Math. Graph Theory, 18:2 (1998), 159–164 | DOI | MR | Zbl

[4] O. V. Borodin, H. J. Broersma, A. N. Glebov, J. Van den Heuvel, “The structure of plane triangulations in terms of clusters and stars”, Diskretn. Anal. Issled. Oper. Ser. 1, 8:2 (2001), 15–39 (in Russian) | MR | Zbl

[5] O. V. Borodin, H. J. Broersma, A. N. Glebov, J. Van den Heuvel, “Minimal degrees and chromatic numbers of squares of planar graphs”, Diskretn. Anal. Issled. Oper. Ser. 1, 8:4 (2001), 9–33 (in Russian) | MR | Zbl

[6] O. V. Borodin, A. O. Ivanova, “Describing $(d-2)$-stars at $d$-vertices, $d\le5$, in normal plane maps”, Discrete Math., 313:17 (2013), 1700–1709 | DOI | MR | Zbl

[7] O. V. Borodin, A. O. Ivanova, “Describing $4$-stars at $5$-vertices in normal plane maps with minimum degree $5$”, Discrete Math., 313:17 (2013), 1710–1714 | DOI | MR | Zbl

[8] O. V. Borodin, A. O. Ivanova, “Light and low $5$-stars in normal plane maps with minimum degree $5$”, Sibirsk. Mat. Zh., 57:3 (2016), 596–602 (in Russian)

[9] O. V. Borodin, A. O. Ivanova, T. R. Jensen, “$5$-stars of low weight in normal plane maps with minimum degree $5$”, Discussiones Mathematicae Graph Theory, 34:3 (2014), 539–546 | DOI | MR | Zbl

[10] O. V. Borodin, A. O. Ivanova, A. V. Kostochka, “Describing faces in plane triangulations”, Discrete Math., 319 (2014), 47–61 | DOI | MR | Zbl

[11] Ph. Franklin, “The four colour problem”, Amer. J. Math., 44 (1922), 225–236 | DOI | MR | Zbl

[12] J. Harant, S. Jendrol', “On the existence of specific stars in planar graphs”, Graphs and Combinatorics, 23 (2007), 529–543 | DOI | MR | Zbl

[13] J. Van den Heuvel, S. McGuinness, “Coloring the square of a planar graph”, J. Graph Theory, 42 (2003), 110–124 | DOI | MR | Zbl

[14] S. Jendrol', T. Madaras, “On light subgraphs in plane graphs of minimal degree five”, Discuss. Math. Graph Theory, 16 (1996), 207–217 | DOI | MR | Zbl

[15] S. Jendrol', T. Madaras, “Note on an existence of small degree vertices with at most one big degree neighbour in planar graphs”, Tatra Mt. Math. Publ., 30 (2005), 149–153 | MR | Zbl

[16] A. Kotzig, “From the theory of eulerian polyhedra”, Mat. Čas., 13 (1963), 20–34 (in Russian) | MR | Zbl

[17] H. Lebesgue, “Quelques conséquences simples de la formule d'Euler”, J. Math. Pures Appl., 19 (1940), 27–43 | MR

[18] P. Wernicke, “Über den kartographischen Vierfarbensatz”, Math. Ann., 58 (1904), 413–426 | DOI | MR | Zbl