Spanning bipartite quadrangulations of even triangulations
Spanning bipartite quadrangulations of even triangulations
复制标题
DOI：
10.1002/jgt.22400
复制
发表时间：
2018-09
影响因子：
0.9
通讯作者：
Atsuhiro Nakamoto;Kenta Noguchi;K. Ozeki
中科院分区：
文献类型：
--
作者：
Atsuhiro Nakamoto;Kenta Noguchi;K. Ozeki
曲面F上的三角剖分(即四边形剖分)是F上的无环图(可能有多条边)的映射，每个面都以长度为3(分别为4)的闭步为界。很容易看出，任何曲面上的每个三角剖分都有一个跨越四边形。Kündgen和Thomassen证明了环面上的每个偶三角剖分G(即每个顶点都有偶次)都有一个生成的非二部四边形，并且如果G有足够大的边宽，则G也有一个二部四边形。本文证明了环面上的偶三角剖分G允许生成二部四边形当且仅当G不以K7为子图，并给出了该问题的一些其他结果。
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.