对偶图的H圈分解和相应的平图4着色  

Hamiltonian cycle decomposition of dual graph and 4-colouring of planar graph

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

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

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

基　　金：国家自然科学基金资助项目(10471096);辽宁省教育厅高等学校科学研究项目(20060842)

摘　　要：阐明了平图中的H圈与对偶图中的森林Fi及顶点4着色的依存关系,提出了一种基于H圈分解的任意平图的顶点4着色方法。介绍了20面体平图中的24个H圈及对偶图中的24个森林Fi及24种顶点4着色方案。讨论了平图及对偶图中的H圈Ci的个数,森林Fi的个数和顶点的4着色方案数。得到任意平图及其对偶图均能分解出H圈和森林Fi,任意平图及其对偶图均为可4着色的。得到了当平图为三角剖分图时,对偶图为多边形组合,H圈个数必大于其对偶图中的H圈的个数。平图为多边形组合时,其对偶图为三角剖分图,H圈的个数必小于对偶图中的H圈的个数。平图中森林Fi的个数或4着色方案数等于对偶图中的H圈的个数;对偶图中的森林Fi′的个数或4着色方案数等于平图中的H圈的个数。The interdependent relation among Hamiltonian cycle in the planar graph,the forests Fi in the dual graph and 4-colouring vertex is illustrated.A method of vertex 4-colouring of the arbitrary planar graph based on the decomposition of the Hamiltonian cycle is proposed.The 24 Hamiltonian cycles in the 20-sided flat map and the 24 forests-Fi in the dual graph and 24 kinds of vertex 4-cdouing program are introduced.The number of Hamiltonian cycles Ci,the number of forests Fi and the number of schemes of vertex 4-colouring in both planar and dual graph are also discussed.It is concluded that the arbitrary planar graph and the dual graph can be decomposed into Hamiltonian cycle and forests-Fi and are 4-colouring.It is also concluded that when the planar graph is triangular subdivision graph,the dual graph is polygon combination and the number of the Hamiltonian cycle is greater than that of Hamiltonian cycle in the dual graph.When the planar graph is polygon combination,the dual graph is triangular subdivision graph and the number of the Hamiltonian cycle will be less than that of Hamiltonian cycle in the dual graph.The number of the forest Fi in the planar graph or the number of schemes of 4-colour is equal to that of Hamiltonian cycle in the dual graph,and the number of the forest Fi in the dual graph or the number of schemes of 4-colour is equal to that of Hamiltonian cycle in the planar graph.

关 键 词：平图 对偶图 4着色 分解 森林 

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