Structures of graphs on surfaces with complete minors

具有完全次要曲面上的图的结构

• 批准号: 21540119
• 负责人: NAKAMOTO Atsuhiro
• 金额: $ 2.91万
• 依托单位: Yokohama National University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21540119/
• 关键词: 離散数学; 位相幾何学的グラフ理論; グラフ; 曲面; 三角形分割; グラフマイナー理論; 完全グラフ; 偶埋め込み; 奇マイナー; サイクルパリティー; Hadwiger予想; ハミルトン閉路; 本型埋め込み

This study deals with a problem : A given graph G on a fixed surface, which complete graph Kn does G have as a minor? This problem is difficult in general, and the problem combining this and graph coloring is well-known as Hadwiger's conjecture, one of the important open problems in the literature. In the research, restricting graphs on surfaces to be triangulations, we characterized the graphs on the orientable surface of genus up to 3 and the nonorientable surface of genus up to 4 containing K_6 as a minor. In order to do so, we used the complete list of irreducible triangulations on those surfaces and the theory for graph transformations.

这项研究涉及一个问题：固定表面上的给定图G，G kn的完整图是辅助的？总体而言，这个问题很困难，并且将其结合起来和图形着色的问题是Hadwiger的猜想，这是文献中重要的开放问题之一。在研究中，限制了表面上的图为三角形，我们表征了最多3属的可定向表面上的图形，以及最多4个含有K_6的属的不可取向表面。为了做到这一点，我们使用了这些表面上不可约三角形的完整列表以及图形转换的理论。

项目成果

2-Orientations of bipartite quadrangulations on the torus

2-环面上二分四边形的方向

• 发表时间: 2010
• 作者: Kobayashi;H.;Kimura;H.;and Yamamoto;S.;Y.Takei;田村 英男;山本けい子;M. van der Put and M.-H. Saito;Hiroshi Kokubu;利根川吉廣;中本敦浩
• 通讯作者: 中本敦浩

Vertex-face curve for bipartite quadrangulations on the torus

环面上二分四边形的点面曲线

• 发表时间: 2010
• 作者: Yutaka Terasawa;Nobuo Yoshida;川久保友超,久保川達也;Syuuji Yamada;K. Aoyama;A. Nakamoto
• 通讯作者: A. Nakamoto

Dominating sets in triangulations on surfaces

• DOI: 10.26493/1855-3974.200.fbe
• 发表时间: 2010-06
• 期刊: Ars Math. Contemp.
• 作者: Hong Liu;M. Pelsmajer

3-trees with a few vertices of degree 3 in 3-connected planar graphs

3 连通平面图中具有几个 3 度顶点的 3 树

• 发表时间: 2009
• 期刊: Discrete Math
• 影响因子: 0.8
• 作者: A. Nakamoto;K. Ota and Y. Oda.
• 通讯作者: K. Ota and Y. Oda.

N-Flips in even triangulations and Dehn twists on the torus

均匀三角测量中的 N 翻转和圆环上的 Dehn 扭曲

• 发表时间: 2011
• 期刊: Discrete Math
• 影响因子: 0.8
• 作者: Y. Higuchi;A. Nakamoto;K. Ota and T.
• 通讯作者: K. Ota and T.