平图中的H圈与对偶图的顶点4着色  

Top 4-colouring of Dual and Hamiltonian Cycle in Plane

作　　者：万禧[1] 李晓毅[2] 

机构地区：[1]安徽理工大学土木建筑学院,安徽淮南232001 [2]沈阳师范大学数学与系统科学学院,沈阳110034

出　　处：《沈阳师范大学学报（自然科学版）》2011年第1期6-8,共3页Journal of Shenyang Normal University:Natural Science Edition

基　　金：国家自然科学基金资助项目(10471096)

摘　　要：阐明了平图的4着色及对偶树与对偶图中的H图的依存关系,以及对偶图的4着色及对偶树与平图中的H圈的依存关系。给出了平面H圈和对偶图顶点4着色的基本思路,得到了对偶图与三角剖分图之间的关系,并利用此关系提出了平图及对偶图的H圈及对偶树的分解方法和顶点4着色方法。这两种方法都是通过给出对偶图成平面的面中心的H圈得到对偶树,并对对偶树进行着色而得到的。介绍了46面体平图及对偶图中的H圈及对偶树的各种分解方案和顶点4着色方案。结果表明:任意平图中的H圈必定将对偶图分解为两棵对偶树,且两棵对偶树的2着色等价于对偶图的顶点4着色,从而使kempe四色猜想"证明"中的错误得以纠正。The interdependent relation between 4-colouring,paired trees in the planar graph and Hamiltonian cycle in the dual,as well as the interdependent relation between 4-colouring,paired trees in the dual and Hamiltonian cycle in the planer graph are described.Given the basic ideas about top 4-colouting of dual and Hamiltoniancycle in the plane,then it can obtain relationship between duas and triangular subdivision graph.Using this relationship,the method of decomposing the planar graph and dual into Hamiltonian cycle and pained trees and the method for top 4-colouring are proposed.These two methods are all according to the Hamiltonian cycle of the center over the dual or planat graph,thus the paired trees are obtained,and finally coloring these paired trees.The different schemes of decomposition into Hamiltonian cycle and pained trees in the planar graph of polyhedron and deferent schemes of 4-colouring the planar graph of polyhedron are presented.The results show that the H cyele in arbitrary planat graph of the H cycle must be decomposed dual to become two paited tree,and two paired trees of the 2-coloring are equivalent to top 4coloring of dual.So that the error in kempe 4-coloring guess proof can be corrected.

关 键 词：平图 4着色 H圈 对偶图 对偶树 

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