Page 315 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 315
GRAPHS, POLYNOMIALS, SURFACES, AND KNOTS (MS-49)
Spanning bipartite subgraphs of triangulations of a surface
Kenta Noguchi, noguchi@rs.tus.ac.jp
Tokyo University of Science, Japan
A triangulation (resp., a quadrangulation) of a surface S is an embedded graph (possibly with
multiple edges and loops) on S with each face bounded by a closed walk of length 3 (resp., 4).
This talk focuses on the relationship between triangulations and quadrangulations of a surface.
(a) Extension of a graph G is the construction of a new graph by adding edges to some
pairs of vertices in G. Obviously, every quadrangulation G of any surface can be extended
to a triangulation by adding a diagonal to each face of G. If we require some properties for
the resulting triangulation, the problem might be difficult and interesting. We prove that every
quadrangulation of any surface can be extended to an Eulerian triangulation. Furthermore, we
give the explicit formula for the number of distinct Eulerian triangulations extended from a
given quadrangulation of a surface. These completely solves the problem raised by Zhang and
He [5].
(b) It is easy to see that every loopless triangulation G of any surface has a quadrangulation
as a spanning subgraph of G. As well as (a), if we require some properties for the resulting
quadrangulation, the problem might be difficult and interesting. Kündgen and Thomassen [1]
proved that every loopless Eulerian triangulation G of the torus has a spanning nonbipartite
quadrangulation, and that if G has sufficiently large face width, then G also has a bipartite
one. We prove that a loopless Eulerian triangulation G of the torus has a spanning bipartite
quadrangulation if and only if G does not have K7 as a subgraph.
This talk is based on the papers [2, 3, 4].
References
[1] A. Kündgen, C. Thomassen, Spanning quadrangulations of triangulated surfaces, Abh.
Math. Semin. Univ. Hambg 87 (2017), 357–368.
[2] A. Nakamoto, K. Noguchi, K. Ozeki, Extension to even triangulations, SIAM J. Discrete
Math. 29 (2015), 2075–2087.
[3] A. Nakamoto, K. Noguchi, K. Ozeki, Spanning bipartite quadrangulations of even trian-
gulations, J. Graph Theory 90 (2019), 267–287.
[4] A. Nakamoto, K. Noguchi, K. Ozeki, Extension to 3-colorable triangulations, SIAM J.
Discrete Math. 33 (2019), 1390–1414.
[5] H. Zhang, X. He, On even triangulations of 2-connected embedded graphs, SIAM J. Com-
put. 34 (2005), 683–696.
313
Spanning bipartite subgraphs of triangulations of a surface
Kenta Noguchi, noguchi@rs.tus.ac.jp
Tokyo University of Science, Japan
A triangulation (resp., a quadrangulation) of a surface S is an embedded graph (possibly with
multiple edges and loops) on S with each face bounded by a closed walk of length 3 (resp., 4).
This talk focuses on the relationship between triangulations and quadrangulations of a surface.
(a) Extension of a graph G is the construction of a new graph by adding edges to some
pairs of vertices in G. Obviously, every quadrangulation G of any surface can be extended
to a triangulation by adding a diagonal to each face of G. If we require some properties for
the resulting triangulation, the problem might be difficult and interesting. We prove that every
quadrangulation of any surface can be extended to an Eulerian triangulation. Furthermore, we
give the explicit formula for the number of distinct Eulerian triangulations extended from a
given quadrangulation of a surface. These completely solves the problem raised by Zhang and
He [5].
(b) It is easy to see that every loopless triangulation G of any surface has a quadrangulation
as a spanning subgraph of G. As well as (a), if we require some properties for the resulting
quadrangulation, the problem might be difficult and interesting. Kündgen and Thomassen [1]
proved that every loopless Eulerian triangulation G of the torus has a spanning nonbipartite
quadrangulation, and that if G has sufficiently large face width, then G also has a bipartite
one. We prove that a loopless Eulerian triangulation G of the torus has a spanning bipartite
quadrangulation if and only if G does not have K7 as a subgraph.
This talk is based on the papers [2, 3, 4].
References
[1] A. Kündgen, C. Thomassen, Spanning quadrangulations of triangulated surfaces, Abh.
Math. Semin. Univ. Hambg 87 (2017), 357–368.
[2] A. Nakamoto, K. Noguchi, K. Ozeki, Extension to even triangulations, SIAM J. Discrete
Math. 29 (2015), 2075–2087.
[3] A. Nakamoto, K. Noguchi, K. Ozeki, Spanning bipartite quadrangulations of even trian-
gulations, J. Graph Theory 90 (2019), 267–287.
[4] A. Nakamoto, K. Noguchi, K. Ozeki, Extension to 3-colorable triangulations, SIAM J.
Discrete Math. 33 (2019), 1390–1414.
[5] H. Zhang, X. He, On even triangulations of 2-connected embedded graphs, SIAM J. Com-
put. 34 (2005), 683–696.
313
