Geodesic
Describing edges in normal plane maps having no adjacent $3$-faces
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 1, pp. 495-500
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The weight $w(e)$ of an edge $e$ in a normal plane map (NPM) is the degree-sum of its end-vertices. An edge $e=uv$ is an $(i,j)$-edge if $d(u)\le i$ and $d(v)\le j$. In 1940, Lebesgue proved that every NPM has a $(3,11)$-edge, or $(4,7)$-edge, or $(5,6)$-edge, where 7 and 6 are best possible. In 1955, Kotzig proved that every $3$-polytope has an edge $e$ with $w(e)\le13$, which bound is sharp. Borodin (1987), answering Erdős' question, proved that every NPM has such an edge. Moreover, Borodin (1991) refined this by proving that there is either a $(3,10)$-edge, or $(4,7)$-edge, or $(5,6)$-edge. Given an NPM, we observe some upper bounds on the minimum weight of all its edges, denoted by $w$, of those incident with a $3$-face, $w^*$, and those incident with two $3$-faces, $w^{**}$. In particular, Borodin (1996) proved that if $w^{**}=\infty$, that is if an NPM has no edges incident with two $3$-faces, then either $w^*\le9$ or $w\le8$, where both bounds are sharp. The purpose of our note is to refine this result by proving that in fact $w^{**}=\infty$ implies either a $(3,6)$- or $(4,4)$-edge incident with a $3$-face, or a $(3,5)$-edge, which description is tight.
Keywords: planar graph, plane map, structure properties, $3$-polytope, weight. 
@article{SEMR_2024_21_1_a21,
     author = {O. V. Borodin and A. O. Ivanova},
     title = {Describing edges in normal plane maps having no adjacent $3$-faces},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {495--500},
     year = {2024},
     volume = {21},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a21/}
}
TY  - JOUR
AU  - O. V. Borodin
AU  - A. O. Ivanova
TI  - Describing edges in normal plane maps having no adjacent $3$-faces
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2024
SP  - 495
EP  - 500
VL  - 21
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a21/
LA  - en
ID  - SEMR_2024_21_1_a21
ER  - 
%0 Journal Article
%A O. V. Borodin
%A A. O. Ivanova
%T Describing edges in normal plane maps having no adjacent $3$-faces
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2024
%P 495-500
%V 21
%N 1
%U http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a21/
%G en
%F SEMR_2024_21_1_a21
O. V. Borodin; A. O. Ivanova. Describing edges in normal plane maps having no adjacent $3$-faces. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 1, pp. 495-500. http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a21/

[1] V.A. Aksenov, O.V. Borodin, A.O. Ivanova, “An extension of Kotzig's theorem”, Discuss. Math. Graph Theory, 36:4 (2016), 889–897 | DOI | MR | Zbl

[2] Ts.Ch-D. Batueva, O.V. Borodin, M.A. Bykov, A.O. Ivanova, O.N. Kazak, D.V. Nikiforov, “Refined weight of edges in normal plane maps”, Discrete Math., 340:11 (2017), 2659–2664 | DOI | MR | Zbl

[3] O.V.Borodin, “Simultaneous colorings of graphs on the plane”, Metody Diskretn. Anal., 45 (1987), 21–27 | MR | Zbl

[4] O.V.Borodin, “On the total coloring of planar graphs”, J. Reine Angew. Math., 394 (1989), 180–185 | DOI | MR | Zbl

[5] O.V.Borodin, “Joint generalization of the Lebesgue and Kotzig theorems on combinatorics of plane maps”, Diskretn. Mat., 3:4 (1991), 24–27 | MR | Zbl

[6] O.V.Borodin, “Joint extension of two Kotzig's theorems on $3$-polytopes”, Combinatorica, 13:1 (1992), 121–125 | DOI | MR | Zbl

[7] O.V.Borodin, “Structure of neighborhoods of edges in planar graphs and simultaneous coloring of vertices, edges and faces”, Math. Notes, 53:5 (1993), 483–489 | DOI | MR | Zbl

[8] O.V. Borodin, “Structural theorem on plane graphs with application to the entire coloring number”, J. Graph Theory, 23:3 (1996), 233–239 | 3.0.CO;2-T class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[9] O.V. Borodin, “More about the weight of edges in planar graphs”, Tatra Mt. Math. Publ., 9 (1996), 11–14 | MR | Zbl

[10] O.V.Borodin, “Colorings of plane graphs: a survey”, Discrete Math., 313:4 (2013), 517–539 | DOI | MR | Zbl

[11] O.V. Borodin, A.N. Glebov, A. Raspaud, “Planar graphs without triangles adjacent to cycles of length from $4$ to $7$ are $3$-colorable”, Discrete Math., 310:20 (2010), 2584–2594 | DOI | MR | Zbl

[12] O.V. Borodin, A.O. Ivanova, “The vertex-face weight of edges in 3-polytopes”, Sib. Math. J., 56:2 (2015), 275–284 | DOI | MR | Zbl

[13] O.V. Borodin, A.O. Ivanova, “Weight of edges in normal plane maps”, Discrete Math., 339:5 (2016), 1507–1511 | DOI | MR | Zbl

[14] O.V. Borodin, A.O. Ivanova, “An improvement of Lebesgue's description of edges in $3$-polytopes and faces in plane quadrangulations”, Discrete Math., 342:6 (2019), 1820–1827 | DOI | MR | Zbl

[15] O.V. Borodin, A.O. Ivanova, A.V. Kostochka, N.N. Sheikh, “Minimax degrees of quasiplane graphs without $4$-faces”, Sib. Èlektron. Mat. Izv., 4 (2007), 435–439 | MR | Zbl

[16] O.V. Borodin, A.V. Kostochka, D.R. Woodall, “List edge and list total colourings of multigraphs”, J. Comb. Theory, Ser. B, 71:2 (1997), 184–204 | DOI | MR | Zbl

[17] B. Ferencová, T. Madaras, “Light graph in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight”, Discrete Math., 310:12 (2010), 1661–1675 | DOI | MR | Zbl

[18] B. Grünbaum, “New views on some old questions of combinatorial geometry”, Colloq. int. Teorie comb. (Rome, 1973), v. I, Accad. Naz. Lincei, Rome, 1976, 451–468 | Zbl

[19] S. Jendrol', M. Maceková, “Describing short paths in plane graphs of girth at least $5$”, Discrete Math., 338:2 (2015), 149–158 | DOI | MR | Zbl

[20] S.Jendrol', H.-J.Voss, “Light subgraphs of graphs embedded in the plane. A survey”, Discrete Math., 313:4 (2013), 406–421 | DOI | MR | Zbl

[21] A. Kotzig, “Contribution to the theory of Eulerian polyhedra”, Matematicko-fyzikálny časopis, 5:2 (1955), 101–103 | MR

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

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