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

Theory on Structure and Coloring of Maximal Planar Graphs (2) Domino Configurations and Extending-Contracting Operations

作　　者：许进[1,2] 

机构地区：[1]北京大学高可信软件技术教育部重点实验室,北京100871 [2]北京大学信息科学技术学院,北京100871

出　　处：《电子与信息学报》2016年第6期1271-1327,共57页Journal of Electronics & Information Technology

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

摘　　要：业已证明四色猜想的数学证明可归结为刻画4-色漏斗型伪唯一4-色极大平面图的特征。为刻画此类极大平面图的结构特征,本文提出一种构造极大平面图的方法——扩缩运算。研究发现：此方法的关键问题是需要清楚一种构形,称为多米诺构形。文中构造性地给出了多米诺构形的充要条件;在此基础上提出并建立了一个图的祖先图与子孙图理论与构造方法。特别证明了：任一最小度≥4的n（≥9）-阶极大平面图必含（n-2）-阶或（n-3）-阶祖先图;给出极大平面图的递推构造法,并用此方法构造出6~12-阶所有最小度≥4的极大平面图。扩缩运算是本系列文章的基石。The first paper of this series of articles revealed that Four-Color Conjecture is hopefully proved mathematically by investigating a special class of graphs, called the 4-chromatic-funnel, pseudo uniquely-4- colorable maximal planar graphs. To characterize the properties of such class of graphs, a novel technique, ＂extending-contracting operation＂, is proposed which can be used to construct maximal planar graphs. The essence of this technique is to study a special kind of configurations, domino configurations. In this paper, a necessary and sufficient condition for a planar graph to be a domino configuration is constructively given, on the basis of which it is proposed to construct the ancestor-graphs and descendent-graphs of a graph. Particularly, it is proved that every maximal planar graph with order n （≥ 9） and minimum degree≥ 4 has an ancestor-graph of order （n - 2） or （n- 3）. Moreover, an approach is put forward to construct maximal planar graphs recursively, by which all maximal planar graphs with order 6-12 and minimum degree≥ 4 are constructed. The extending-contracting operation constitutes the foundation in this series of articles.

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

分 类 号：O157.5[理学—数学]