| Heawood图的一对对偶树的分解和4-着色 |
| |
| 引用本文： | 侴万禧,孟宪涛. Heawood图的一对对偶树的分解和4-着色[J]. 沈阳师范大学学报(自然科学版), 2011, 29(4): 474-477. DOI: 10.3969/j.issn.1673-5862.2011.04.002 |
| |
| 作者姓名： | 侴万禧 孟宪涛 |
| |
| 作者单位： | 1. 安徽理工大学土木建筑学院,安徽淮南,232001
2. 沈阳师范大学数学与系统科学学院,沈阳,110034 |
| |
| 基金项目： | 国家自然科学基金资助项目(10471096) |
| |
| 摘 要： | 阐明了任意平图的4-着色的主要思路,给出了对偶树的定义。对偶图中的一对对偶树与对偶图的Hamilton路径相互依存,提出了任意平图的4-着色的方法步骤。得到利用上述方法得到的一对对偶树及具有的性质。介绍了Heawood图的由来和基本特点、Heawood图的4-着色的2种方法步骤,通过对偶图的2个区域的划分,实施了Heawood图的4-着色,借助于Heawood图的对偶图的Hamilton路径的分解构造了2棵对偶树。借助于此方法所得的Heawood图的25个顶点的4-着色方案达到236个,从而使Kempe的4-cc猜想"证明"中的漏洞得到弥补。
|
| 关 键 词： | 对偶树 分解 4-着色 Heawood图 平图 |
Decomposition and 4-colouring of apair of dual trees of Heawood graph |
| |
| CHOU Wan-xi,MENG Xian-tao. Decomposition and 4-colouring of apair of dual trees of Heawood graph[J]. Journal of Shenyang Normal University(Natural Science Edition), 2011, 29(4): 474-477. DOI: 10.3969/j.issn.1673-5862.2011.04.002 |
| |
| Authors: | CHOU Wan-xi MENG Xian-tao |
| |
| Affiliation: | CHOU Wan-xi1,MENG Xian-tao2(1.School of Civil Engineering and Architecture,Anhui University of Science and Technology,Huainan 232001,China,2.School of Mathematics and Systems Science,Shenyang Normal University,Shenyang 110034,China) |
| |
| Abstract: | This paper clarifies the basic concept concerning the 4-colouring of arbitrary plannar graph,and gives a definition of dual trees.A pair of dual trees in the dual graph and the Hamilton path on the dual graph are interdependent,and so a kind of 4-colouring of arbitrary plannar graph is given.Based on the above mentioned theory,this paper gets a pair of dual trees and its property.And then, the origin and basic characteristics of Heawood graph are describled,and two methods and steps of 4-coloring of Heawood... |
| |
| Keywords: | dual trees decomposition 4-coloring Heawood graph plannar path |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
