Premium
Spanning bipartite quadrangulations of even triangulations
Author(s) -
Nakamoto Atsuhiro,
Noguchi Kenta,
Ozeki Kenta
Publication year - 2019
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22400
Subject(s) - mathematics , combinatorics , bipartite graph , triangulation , torus , vertex (graph theory) , bounded function , point set triangulation , enhanced data rates for gsm evolution , graph , geometry , delaunay triangulation , mathematical analysis , computer science , telecommunications
A triangulation (resp., a quadrangulation ) on a surface F is a map of a loopless graph (possibly with multiple edges) on F with each face bounded by a closed walk of length 3 (resp., 4). It is easy to see that every triangulation on any surface has a spanning quadrangulation. Kündgen and Thomassen proved that every even triangulation G (ie, each vertex has even degree) on the torus has a spanning nonbipartite quadrangulation, and that if G has sufficiently large edge width, then G also has a bipartite one. In this paper, we prove that an even triangulation G on the torus admits a spanning bipartite quadrangulation if and only if G does not have K 7 as a subgraph, and moreover, we give some other results for the problem.