Heawood图的一对对偶树的分解和4-着色

阐明了任意平图的4-着色的主要思路,给出了对偶树的定义。对偶图中的一对对偶树与对偶图的Hamilton路径相互依存,提出了任意平图的4-着色的方法步骤。得到利用上述方法得到的一对对偶树及具有的性质。介绍了Heawood图的由来和基本特点、Heawood图的4-着色的2种方法步骤,通过对偶图的2个区域的划分,实施了Heawood图的4-着色,借助于Heawood图的对偶图的Hamilton路径的分解构造了2棵对偶树。借助于此方法所得的Heawood图的25个顶点的4-着色方案达到236个,从而使Kempe的4-cc猜想"证明"中的漏洞得到弥补。

平面图正常4-着色数的一个计算公式

四色定理等价于任何准极大平面图 ( near-triangulation)至少有一个正常 4 -着色 .给出了对任意给定的准极大平面图都能准确求出其正常 4 -着色数的计算公式 ,该公式的复杂性揭示了四色定理本身所蕴涵的难度 .

平面图的4-着色的简单布尔方程表示

如果一个无环平面图 G至多有一个非三角形的面 ,则称 G为准极大平面图 ( near-trian-gulation) .本文给出了极大平面图和准极大平面图 4 -着色的一类布尔方程表示式 ,该布尔方程所含变元较少 ,结构简单 ,具有良好的递归性质 ,为利用计算机寻找给定平面图的 4 -着色提供了很好的算法 .

一类极大平面图4-着色布尔方程组

对极大平面图的4-着色布尔方程组F1d1(x1,x2,…,xn)=1 F2d2(x1,x2,…,xn)=1……Fndn(x1,x2,…,xn)=1进行研究,得到了该布尔方程组的5条性质,并且给出了求极大平面图4-着色全部解的一个算法.

一类4——可着色的极大平面图

定义了极大平面图的分离圈和分离带，并讨论了一些简单的平面图的着色问题，又给出了一类４－可着色的极大平面图．

多重图M_n^((r))的边着色研究

定义了多重图的R(k,n:p)-边着色,并利用正交拉丁方和矩阵的乘法证明了当m≡0(mod2)时,图M_(2m)^((r))是R(2,m:4)-边着色图。

四色定理论证

用离散数学之图论证明"四色猜想",巧妙而深层次地应用数学归纳法和换色法,解决了肯泊(A.Kempe)百多年前提出"不可避免构形集"中的一个地域有五个邻域的情况的所谓"可约性"问题,同时指出了1890年希伍德(P.Heawood)举出的25阶反例(当时,他以此说明"四色猜想"不成立,而"五色定理"成立)与本文中的一种可换色(即"可约性")的典型实例类同,进而简捷而理想地证明了"四色猜想"是成立的,使"四色定理"得到科学的论证。