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

来源：电子与信息学报杂志2016年第6期北京时间：

作者：许进

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

关键词：极大平面图, 扩缩运算, 多米诺构形, 祖先图, 子孙图, 递推构造法

基金资助：国家973规划项目(2013CB329600)，国家自然科学基金(61372191, 61472012, 61472433, 61572046, 61502012, 61572492, 61572153, 61402437)