极大平面图的结构与着色理论（2）多米诺构形与扩缩运算

• 作者: 许进
• 来源期刊: 电子与信息学报
• 学科: 数学
• 关键词: 极大平面图 扩缩运算 多米诺构形 祖先图 子孙图 递推构造法
• 年，卷（期）: 2016,（6）
• 所属期刊栏目: 论文
• 页码范围: 1271-1296
• 页数: 26页
• 分类号: O157.5
• 字数: 15199字
• 语种: 中文
• DOI: 10.11999/JEIT160224

摘要

业已证明四色猜想的数学证明可归结为刻画4-色漏斗型伪唯一4-色极大平面图的特征。为刻画此类极大平面图的结构特征，本文提出一种构造极大平面图的方法扩缩运算。研究发现：此方法的关键问题是需要清楚一种构形，称为多米诺构形。文中构造性地给出了多米诺构形的充要条件；在此基础上提出并建立了一个图的祖先图与子孙图理论与构造方法。特别证明了：任一最小度4的(9)n -阶极大平面图必含(2)n -阶或(3)n -阶祖先图；给出极大平面图的递推构造法，并用此方法构造出6~12-阶所有最小度4的极大平面图。扩缩运算是本系列文章的基石。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许进	北京大学高可信软件技术教育部重点实验室	33	247	8.0	15.0