Article in press
Authors:
Title:
Tight description of faces in toroidal graphs with minimum degree at least 4
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-06-07 , Revised: 2023-10-26 , Accepted: 2023-10-27 , Available online: 2023-11-17 , https://doi.org/10.7151/dmgt.2529
Abstract:
The degree $d(x)$ of a vertex or face $x$ in a graph $G$ is the
number of incident edges. A face $f=v_1\cdots v_{d(f)}$ in a graph
$G$ on the plane or other orientable surface is of type
$(k_1,k_2,\ldots)$ if $d(v_i)\le k_i$ for each $i$. By $\delta$
we denote the minimum vertex-degree of $G$.
It follows from the classical theorem by Lebesgue (1940) that
every plane triangulation with $\delta\ge4$ has a 3-face of types
$(4,4,\infty)$, $(4,5,19)$, $(4,6,11)$, $(4,7,9)$, $(5,5,9)$, or
$(5,6,7)$. In 1999, Jendrol' gave a similar description:
``$(4,4,\infty)$, $(4,5,13)$, $(4,6,17)$, $(4,7,8)$, $(5,5,7)$,
$(5,6,6)$'' and conjectured that ``$(4,4,\infty)$, $(4,5,10)$,
$(4,6,15)$, $(4,7,7)$, $(5,5,7)$, $(5,6,6)$'' holds. In 2002,
Lebesgue's description was strengthened by Borodin to
``$(4,4,\infty)$, $(4,5,17)$, $(4,6,11)$, $(4,7,8)$, $(5,5,8)$,
$(5,6,6)$''. In 2014, we obtained the following tight description,
which, in particular, disproves the above mentioned conjecture by
Jendrol': ``$(4,4,\infty)$, $(4,5,11)$, $(4,6,10)$, $(4,7,7)$,
$(5,5,7)$, $(5,6,6)$'', and recently proved another tight
description of faces in plane triangulations with $\delta\ge4$:
``$(4,4,\infty)$, $(4,6,10)$, $(4,7,7)$, $(5,5,8)$, $(5,6,7)$''.
It follows from Lebesgue's theorem of 1940 that every plane
3-connected quadrangulation has a face of one of the types
$(3,3,3,\infty)$, $(3,3,4,11)$, $(3,3,$ $5,7)$, $(3,4,4,5)$.
Recently, we improved this description to ``$(3,3,3,\infty)$,
$(3,3,4,9)$, $(3,3,5,6)$, $(3,4,4,5)$'', where all parameters
except possibly $9$ are best possible and 9 cannot go down below 8.
In 1995, Avgustinovich and Borodin proved the following tight
description of the faces of torus quadrangulations with
$\delta\ge3$: ``$(3,3,3,\infty)$, $(3, 3,$ $4, 10)$, $(3, 3, 5, 7)$,
$(3, 3, 6, 6)$, $(3, 4, 4, 6)$, $(4, 4, 4, 4)$''.
Recently, we proved that every triangulation with $\delta\ge4$ of
the torus has a face of one of the types $(4,4,\infty)$,
$(4,6,12)$, $(4,8,8)$, $(5,5,8)$, $(5,6,7)$, or $(6,6,6)$, which
description is tight.
The purpose of this paper is to prove that every graph with
$\delta\ge4$ that admits a closed $2$-cell embedding on the torus
has a face of one of the types $(4,4,4,4)$, $(4,4,\infty)$,
$(4,5,16)$, $(4,6,12)$, $(4,8,8)$, $(5,5,8)$, $(5,6,7)$, or
$(6,6,6)$, where all parameters are best possible.
Keywords:
plane graph, toroidal graph, degree, face, structure
References:
- S.V. Avgustinovich and O.V. Borodin, Edge neighborhoods in normal maps, Diskretn. Anal. Issled. Oper. 2(3) (1989) 9–12, in Russian.
Translation in: Operations Research and Discrete Analysis, A.D. Korshunov (Eds), Math. Appl. (N.Y.) 391 (Springer Netherlands, 1997) 17–22.
https://doi.org/10.1007/978-94-011-5678-3_3 - O.V. Borodin, Solution of problems of Kotzig and Grünbaum concerning the isolation of cycles in planar graphs, Mat. Zametki 46(5) (1989) 9–12, in Russian.
Translation in: Math. Notes 46(5) (1989) 835–837.
https://doi.org/10.1007/BF01139613 - O.V. Borodin, An improvement of Lebesgues theorem on the structure of minor faces of $3$-polytopes, Diskretn. Anal. Issled. Oper. 9(3) (2002) 29–39, in Russian.
- O.V. Borodin, Colorings of plane graphs: A survey, Discrete Math. 313 (2013) 517–539.
https://doi.org/10.1016/j.disc.2012.11.011 - O.V. Borodin and A.O. Ivanova, Describing $3$-faces in normal plane maps with minimum degree $4$, Discrete Math. 313 (2013) 2841–2847.
https://doi.org/10.1016/j.disc.2013.08.028 - O.V. Borodin and A.O. Ivanova, Combinatorial structure of faces in triangulated $3$-polytopes with minimum degree $4$, Sib. Math. J. 55 (2014) 12–18.
https://doi.org/10.1134/S0037446614010030 - O.V. Borodin, A.O. Ivanova, New results about the structure of plane graphs: A survey, AIP Conference Proceedings 1907 (2017) 030051, 10.1063/1.5012673.
- O.V. Borodin and A.O. Ivanova, An improvement of Lebesgue's description of edges in $3$-polytopes and faces in plane quadrangulations, Discrete Math. 342 (2019) 1820–1827.
https://doi.org/10.1016/j.disc.2019.02.019 - O.V. Borodin and A.O. Ivanova, Tight description of faces in torus triangulations with minimum degree $5$, Sib. Èlektron. Mat. Izv. 18 (2021) 1475–1481.
https://doi.org/10.33048/semi.2021.18.110 - O.V. Borodin and A.O. Ivanova, Combinatorial structure of faces in triangulations on surfaces, Sib. Math. J. 63 (2022) 662–669.
https://doi.org/10.1134/S0037446622040061 - O.V. Borodin and A.O. Ivanova, Another tight description of faces in plane triangulations with minimum degree $4$, Discrete Math. 345(9) (2022) 112964.
https://doi.org/10.1016/j.disc.2022.112964 - O.V. Borodin, A.O. Ivanova and A.V. Kostochka, Describing faces in plane triangulations, Discrete Math. 319 (2014) 47–61.
https://doi.org/10.1016/j.disc.2013.11.021 - D.W. Cranston and D.B. West, An introduction to the discharging method via graph coloring, Discrete Math. 340 (2017) 766–793.
https://doi.org/10.1016/j.disc.2016.11.022 - B. Grünbaum, Polytopal graphs, in: Studies in Graph Theory, Part II, D.R. Fulkerson (Ed(s)), (MMA Studies in Mathematics 12 1975) 201–224.
- M. Horňák and S. Jendrol', Unavoidable sets of face types for planar maps, Discuss. Math. Graph Theory 16 (1996) 123–141.
https://doi.org/10.7151/dmgt.1028 - S. Jendrol', Triangles with restricted degrees of their boundary vertices in plane triangulations, Discrete Math. 196 (1999) 177–196.
https://doi.org/10.1016/S0012-365X(98)00172-1 - S. Jendrol' and H.-J. Voss, Light subgraphs of graphs embedded in the plane – A survey, Discrete Math. 313 (2013) 406–421.
https://doi.org/10.1016/j.disc.2012.11.007 - A. Kotzig, From the theory of Euler's polyhedrons, Mat.-Fyz. Čas. 13 (1963) 20–34, in Russian.
- H. Lebesgue, Quelques conséquences simples de la formule d'Euler, J. Math. Pures Appl. 19 (1940) 27–43.
- B. Mohar, R. Škrekovski and H.-J. Voss, Light subgraphs in planar graphs of minimum degree $4$ and edge-degree $9$, J. Graph Theory 44 (2003) 261–295.
https://doi.org/10.1002/jgt.10144 - O. Ore and M.D. Plummer, Cyclic coloration of plane graphs, in: Recent Progress in Combinatorics, W.T. Tutte (Ed(s)), (Academic Press, New York 1969) 287–293.
Close