Soft 3-stars in sparse plane graphs

O. V. Borodin ; A. O. Ivanova

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 1863-1868.

Résumé

We consider plane graphs with large enough girth $g$, minimum degree $\delta$ at least 2 and no $(k+1)$-paths consisting of vertices of degree 2, where $k\ge1$. In 2016, Hudák, Maceková, Madaras, and Široczki studied the case $k=1$, which means that no two 2-vertices are adjacent, and proved, in particular, that there is a 3-vertex whose all three neighbors have degree 2 (called a soft 3-star), provided that $g\ge10$, which bound on $g$ is sharp. For the first open case $k=2$ it was known that a soft 3-star exists if $g\ge14$ but may not exist if $g\le12$. In this paper, we settle the case $k=2$ by presenting a construction with $g=13$ and no soft 3-star. For all $k\ge3$, we prove that soft 3-stars exist if $g\ge4k+6$ but, as follows from our construction, possibly not exist if $g\le3k+7$. We conjecture that in fact soft 3-stars exist whenever $g\ge3k+8$.

Détail

Keywords: plane graph, structure properties, girth, tight description, weight, height, 3-star, soft 3-star.

Bibliographie

[1] V.A. Aksenov, O.V. Borodin, A.O. Ivanova, “Weight of $3$-paths in sparse plane graphs”, Electron. J. Comb., 22:3 (2015), P3.28 | MR | Zbl

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

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

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

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

[6] O.V. Borodin, A.O. Ivanova, “Light $3$-stars in sparse plane graphs”, Sibe. Electron. Mat. Izv., 15 (2018), 1344–1352 | MR | Zbl

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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