Spanning bipartite quadrangulations of even triangulations
Atsuhiro Nakamoto, Kenta Noguchi, Kenta Ozeki · Journal of Graph Theory · 2018
Abstract A triangulation (resp., a quadrangulation ) on a surface is a map of a loopless graph (possibly with multiple edges) on 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 (ie, each vertex has even degree) on the torus has a spanning nonbipartite quadrangulation, and that if has sufficiently large edge width, then also has a bipartite one. In this paper, we prove that an even triangulation on the torus admits a spanning bipartite quadrangulation if and only if does not have as a subgraph, and moreover, we give some other results for the problem.