Geodesic
Light 3-stars in sparse plane graphs
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 15 (2018), pp. 1344-1352.

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

A $k$-star $S_k(v)$ in a plane graph $G$ consists of a central vertex $v$ and $k$ its neighbor vertices. The height $h(S_k(v))$ and weight $w(S_k(v))$ of $S_k(v)$ is the maximum degree and degree-sum of its vertices, respectively. The height $h_k(G)$ and weight $w_k(G)$ of $G$ is the maximum height and weight of its $k$-stars. Lebesgue (1940) proved that every 3-polytope of girth $g$ at least 5 has a 2-star (a path of three vertices) with $h_2=3$ and $w_2=9$. Madaras (2004) refined this by showing that there is a 3-star with $h_3=4$ and $w_3=13$, which is tight. In 2015, we gave another tight description of 3-stars for girth $g=5$ in terms of degree of their vertices and showed that there are only these two tight descriptions of 3-stars. In 2013, we gave a tight description of $3^-$-stars in arbitrary plane graphs with minimum degree $\delta$ at least 3 and $g\ge3$, which extends or strengthens several previously known results by Balogh, Jendrol', Harant, Kochol, Madaras, Van den Heuvel, Yu and others and disproves a conjecture by Harant and Jendrol' posed in 2007. There exist many tight results on the height, weight and structure of $2^-$-stars when $\delta=2$. In 2016, Hudák, Maceková, Madaras, and Široczki considered the class of plane graphs with $\delta=2$ in which no two vertices of degree 2 are adjacent. They proved that $h_3=w_3=\infty$ if $g\le6$, $h_3=5$ if $g=7$, $h_3=3$ if $g\ge8$, $w_3=10$ if $g=8$ and $w_3=3$ if $g\ge9$. For $g=7$, Hudák et al. proved $11\le w_3\le20$. The purpose of our paper is to prove that every plane graph with $\delta=2$, $g=7$ and no adjacent vertices of degree 2 has $w_3=12$.
Keywords: plane graph, structure properties, tight description, weight, 3-star, girth. 
@article{SEMR_2018_15_a76,
     author = {O. V. Borodin and A. O. Ivanova},
     title = {Light 3-stars in sparse plane graphs},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {1344--1352},
     publisher = {mathdoc},
     volume = {15},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2018_15_a76/}
}
TY  - JOUR
AU  - O. V. Borodin
AU  - A. O. Ivanova
TI  - Light 3-stars in sparse plane graphs
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2018
SP  - 1344
EP  - 1352
VL  - 15
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2018_15_a76/
LA  - en
ID  - SEMR_2018_15_a76
ER  - 
%0 Journal Article
%A O. V. Borodin
%A A. O. Ivanova
%T Light 3-stars in sparse plane graphs
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2018
%P 1344-1352
%V 15
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2018_15_a76/
%G en
%F SEMR_2018_15_a76
O. V. Borodin; A. O. Ivanova. Light 3-stars in sparse plane graphs. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 15 (2018), pp. 1344-1352. http://geodesic.mathdoc.fr/item/SEMR_2018_15_a76/

[1] V.A. Aksenov, O.V. Borodin, A.O. Ivanova, “Weight of $3$-paths in sparse plane graphs”, Electronic J. Combin., 22:3 (2015), #P3.28 http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i3p28 | MR | Zbl

[2] 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

[3] K. Ando, S. Iwasaki, A. Kaneko, “Every $3$-connected planar graph has a connected subgraph with small degree sum”, Annual Meeting of Mathematical Society of Japan (1993) (in Japanese)

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

[5] 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

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

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

[8] O.V. Borodin, “The structure of neighborhoods of an edge in planar graphs and the simultaneous coloring of vertices, edges and faces”, Mat. Zametki, 53:5 (1993), 35–47 (in Russian) | MR | Zbl

[9] O.V. Borodin, “Minimal vertex degree sum of a $3$-path in plane maps”, Discuss. Math. Graph Theory, 17:2 (1997), 279–284 | DOI | MR | Zbl

[10] 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

[11] O.V. Borodin, A.O. Ivanova, “List injective colorings of planar graphs”, Discrete Math., 311:2–3 (2011), 154–-165 | DOI | MR | Zbl

[12] 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

[13] O.V. Borodin, A.O. Ivanova, “Describing tight descriptions of 3-paths in triangle-free normal plane maps”, Discrete Math., 338:11 (2015), 1947–1952 | DOI | MR | Zbl

[14] O.V. Borodin, A.O. Ivanova, “Low edges in 3-polytopes”, Discrete Math., 338:12 (2015), 2234–2241 | DOI | MR | Zbl

[15] O.V. Borodin, A.O. Ivanova, “An analogue of Franklin's Theorem”, Discrete Math., 339:10 (2016), 2553–2556 | DOI | MR | Zbl

[16] O.V. Borodin, A.O. Ivanova, “Light neighborhoods of $5$-vertices in $3$-polytopes with minimum degree $5$”, Sib. Elektron. Math. Reports, 13 (2016), 584–591 | DOI | MR | Zbl

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

[18] O.V. Borodin, A.O. Ivanova, “Low stars in normal plane maps with minimum degree $4$ and no adjacent $4$-vertices”, Discrete Math., 339:2 (2016), 923–930 | DOI | MR | Zbl

[19] O.V. Borodin, A.O. Ivanova, “Light and low $5$-stars in normal plane maps with minimum degree $5$”, Sib. Math. J., 57:3 (2016), 470–475 | DOI | MR | Zbl

[20] O.V. Borodin, A.O. Ivanova, “New results about the structure of plane graphs: a survey”, AIP Conference Proceedings, 1907, 2017, 030051 | DOI | MR

[21] O.V. Borodin, A.O. Ivanova, “On light neighborhoods of 5-vertices in 3-polytopes with minimum degree $5$”, Discrete Math., 340:9 (2017), 2234–2242 | DOI | MR | Zbl

[22] O.V. Borodin, A.O. Ivanova, “All tight descriptions of $3$-stars in 3-polytopes with girth $5$”, Discuss. Math. Graph Theory, 37:1 (2017), 5–12 | DOI | MR | Zbl

[23] O.V. Borodin, A.O. Ivanova, “Low $5$-stars in normal plane maps with minimum degree $5$”, Discrete Math., 340:2 (2017), 18–22 | DOI | MR | Zbl

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

[25] O.V. Borodin, A.O. Ivanova, T.R. Jensen, A.V. Kostochka, M.P. Yancey, “Describing $3$-paths in normal plane maps”, Discrete Math., 313:23 (2013), 2702–2711 | DOI | MR | Zbl

[26] O.V. Borodin, A.O. Ivanova, O.N. Kazak, “Describing neighborhoods of $5$-vertices in $3$-polytopes with minimum degree $5$ and without vertices of degrees from $7$ to $11$”, Discuss. Math. Graph Theory, 38:3 (2018), 615–625 | DOI | MR | Zbl

[27] O.V. Borodin, A.O. Ivanova, O.N. Kazak, E.I. Vasil'eva, “Heights of minor $5$-stars in $3$-polytopes with minimum degree $5$ and no vertices of degree $6$ and $7$”, Discrete Math., 341:3 (2018), 825–829 | DOI | MR | Zbl

[28] O.V. Borodin, A.O. Ivanova, A.V. Kostochka, “Tight descriptions of $3$-paths in normal plane maps”, J. Graph Theory, 85:1 (2017), 115–132 | DOI | MR | Zbl

[29] O.V. Borodin, A.O. Ivanova, D.V. Nikiforov, “Low and light minor 5-stars in 3-polytopes with minimum degree $5$ and restrictions on the degrees of major vertices”, Sib. Math. J., 58:4 (2017), 600–605 | DOI | MR | Zbl

[30] O.V. Borodin, A.O. Ivanova, D.V. Nikiforov, “Low minor $5$-stars in $3$-polytopes with minimum degree $5$ and no $6$-vertices”, Discrete Math., 340:7 (2017), 1612–1616 | DOI | MR | Zbl

[31] O.V. Borodin, A.O. Ivanova, D.V. Nikiforov, “Describing neighborhoods of $5$-vertices in a class of $3$-polytopes with minimum degree $5$”, Sib. Math. J., 59:1 (2018), 43–49 | DOI | MR | Zbl

[32] B. Ferencová, T. Madaras, “Light graphs 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

[33] Ph. Franklin, “The four-color problem”, Amer. J. Math., 44:3 (1922), 225–236 | DOI | MR | Zbl

[34] J. Harant, S. Jendrol', “On the Existence of Specific Stars in Planar Graphs”, Graphs and Combinatorics, 23:5 (2007), 529–543 | DOI | MR | Zbl

[35] P. Hudák, M. Maceková, T. Madaras, P. Široczki, “Light graphs in planar graphs of large girth”, Discuss. Math. Graph Theory, 36:1 (2016), 227–-238 | DOI | MR | Zbl

[36] S. Jendrol', “A structural property of convex $3$-polytopes”, Geom. Dedicata, 68:1 (1997), 91–99 | DOI | MR | Zbl

[37] S. Jendrol', “Paths with restricted degrees of their vertices in planar graphs”, Czechoslovak Math. J., 49(124):3 (1999), 481–490 | DOI | MR | Zbl

[38] 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

[39] S. Jendrol', M. Maceková, M. Montassier, R. Soták, “Optimal unavoidable sets of types of $3$-paths for planar graphs of given girth”, Discrete Math., 339:2 (2016), 780–789 | DOI | MR | Zbl

[40] S. Jendrol', M. Maceková, M. Montassier, R. Soták, “$3$-paths in graphs with bounded average degree”, Discuss. Math. Graph Theory, 36:2 (2016), 339–353 | DOI | MR | Zbl

[41] S. Jendrol', M. Maceková, R. Soták, “Note on $3$-paths in plane graphs of girth $4$”, Discrete Math., 338:9 (2015), 1643–1648 | DOI | MR | Zbl

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

[43] 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

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

[45] T. Madaras, “On the structure of plane graphs of minimum face size $5$”, Discuss. Math. Graph Theory, 24:3 (2004), 403–411 | DOI | MR | Zbl

[46] T. Madaras, “Two variations of Franklin’s theorem”, Tatra Mt. Math. Publ., 36 (2007), 61–70 | MR | Zbl

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

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