Heawood反例图的全部四着色  

All 4-Colorpings of Heawood's Counterexample

作　　者：许寿椿[1] 程斌[1] 杨宁[1] 宝力高[1] 丁保岭[1] 

机构地区：[1]中央民族大学理学院,北京100081

出　　处：《中央民族大学学报（自然科学版）》2007年第4期299-303,共5页Journal of Minzu University of China(Natural Sciences Edition)

摘　　要：本文首次报告了Heawood反例图的全部四着色.它可以用一个树林来描述.树林的每个分支是一棵四着色树.四着色树是一个根树.根节点Cr是Heawood反例图的一个四着色.根树其它节点都是经过一个或多个二色变换从Cr变来的.Heawood反例图有37个四着色树.其中有35个偶四色树(包括24个是仅有根结点的退化型四色树),2个奇四色树.偶四着色总计112,奇四着色总计144,全部四着色总共256个.这些结果都是用Maple编程得到的.In this paper all of 4-colorpings of Heawood＇s counterexample are given. It can be described by a forest. Each component of the forest is a Tfc （Tree of 4-colorings ）. The Tfc is a rooted tree. The rooted note is a 4-colopings of Heawood＇ s counterexample, Cr. Each of other notes is induced by a Kempe＇s interchange or some Kempe＇s interchanges from Cr. The Heawood＇s counterexample graph has 37 trees of 4-colorings. In where there are 35 even Tfc and 2 odd Tfc. The Heawood＇ s counterexample graph has 112 even 4-colorings and 144 odd 4-colorings.

关 键 词：四着色算法 极大平面图 色多项式 四色不变量 

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