Structures of locally planar 4-colorable graphs on surfaces

表面上局部平面四色图的结构

• 批准号: 21K03337
• 负责人: 中本 敦浩
• 金额: $ 2.75万
• 依托单位: Yokohama National University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2021
• 资助国家: 日本
• 起止时间: 2021-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-21K03337/
• 关键词: グラフ; representativity; 局所平面的グラフ; 閉曲面; 頂点彩色; 染色数; 局所平面グラフ; 三角形分割; グラフ彩色; 曲面; 彩色

四色定理により，任意の平面的グラフは4-彩色可能であることが，Appel-Harkenによって証明された．一方，球面以外の閉曲面上のグラフには，4-彩色不可能なものも存在するが，閉曲面Fのグラフの染色数は，Fのオイラー数のみで定まるある定数でその上界が抑えられることが知られている．球面以外の閉曲面F上のグラフGは，Gの非可縮閉路の長さが十分に大きければ（Gが局所平面的であれば），Gは5-彩色可能であることがThomassenによって示された．これに対して，F上の局所平面的グラフで4-彩色不可能なグラフクラスは，次の２つのみが知られている．（１）局所平面的なFisk三角形分割，（２）向き付け不可能な閉曲面の四角形分割の面細分となる偶三角形分割．本研究では，それ以外のグラフクラスが存在するのか，それとも存在しないのかという問題に焦点をあてて研究を行う．私はこれまで，閉曲面の四角形分割の染色数や，宮三角形分割の染色数の研究に長い間取り組んできており，そこで得られた知見がこのような研究テーマに大いに役に立つのではないかと考えられる．

Appel-Harken 使用四色定理证明了任何平面图都可以是四色的。另一方面，除了球体之外的封闭曲面上的一些图不能是4色的，但是封闭曲面F的图上的污点数的上限被仅由F的欧拉数确定的某个常数所抑制。据了解托马森表明，如果 G 的不可压缩循环的长度足够大（如果 G 是局部平面的），则除球体之外的封闭曲面 F 上的图 G 可以是 5 色的。另一方面，对于 F 上不能是 4 色的局部平面图，只有以下两个图类是已知的。 （1）局部平面菲斯克三角剖分；（2）均匀三角剖分，它是无法定向的封闭曲面的矩形划分的曲面细分。在本研究中，我们将重点关注其他图类是否存在的问题。我长期从事封闭曲面四边形分割的污点数量和封闭曲面的三角形分割的污点数量的研究，相信在那里获得的知识可能对此类研究主题有很大帮助将会完成。

项目成果

ガイダンス離散数学

指导离散数学

• 发表时间: 2023
• 作者: 中本敦浩;小関健太
• 通讯作者: 小関健太

Geometric quadrangulations with spirality

具有螺旋的几何四边形

• 发表时间: 2022
• 作者: Atsuhiro Nakamoto

Geometric quadrangulation of a polygon with spirality

螺旋多边形的几何四边形

• 发表时间: 2022
• 作者: Atsuhiro Nakamoto

Flip distance of triangulations on surfaces

曲面上三角剖分的翻转距离

• 发表时间: 2021
• 作者: Atsuhiro Nakamoto

中本敦浩のホームページ

中本笃宏的主页