基于平图的H圈分解的对偶图的四着色

Planar Graph Based 4-Colouring of Dual Graph is H-cycle Decomposition

阐明了平图中的H圈与对偶图中的森林Fi及顶点四着色的依存关系,提出了一种基于H圈分解的任意平图的顶点四着色方法。介绍了20面体平图中的90个H圈及对偶图中的90个森林Fi及90种顶点四着色方案。讨论了平图及对偶图中的H圈Ci的个数,森林Fi的个数和顶点的四着色方案数。

The interdependent relation between Hamiltonian cycle,the forest Fi and vertex 4-colour in both plane and dual is described.A method of 4-colouring the vertices of the arbitrary planar graph is proposed.The 20-sided flat map of the 90 Hamiltonian cycle and the dual graph of the 90 forest-Fiand 90 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-colour in both planar graph and dual are discussed.