图的Hamilton性、Ramsey数和四色问题的研究

论文摘要

本文分为三章对有限图的Hamilton性、Ramsey数和四色猜想三方面的问题分别作了讨论。 在第一章里我们讨论了图的Hamilton性问题。文章第一节首先介绍了Hamilton图的概念和一些相关的定理。第二节对Ore定理的结论进行了推广,证明了2连通简单图G,若独立数α≥3且对G中任意一个独立集{x,y,z}有dx+dy+dz≥3ν/2,则G是Hamilton图,同时还证明了G是2连通简单图,若G的独立数α≥3且对G中任意一个独立集{x,y,z}有dx+dy+dz≥ν+α,则G是Hamilton图。第三节我们首先定义了平衡二部图的一个半闭包G+,并证明了若一个简单平衡二部图G的半闭包G+为完全二部图,则G为Hamilton图。然后,我们构作了一类度极大的非Hamilton简单二部图bm, n,证明了与1972年Chvátal得到的一个结论类似的结果:若G是ν≥4的非Hamilton简单平衡二部图,它一定度弱于某个度极大的非Hamilton简单二部图bm, n。第四节主要讨论部数为3和4的几乎正则多部竞赛图的Hamilton性质,证明几乎正则非平衡4部竞赛图T,如果r≥8（其中r=max{Vi|i=1,2,3,4}）,并且T有一个圈因子,则T是Hamilton的;几乎正则平衡3部竞赛图T,如果r≥10,r≠11（其中r=max{Vi|i=1,2,3}）,并且T有一个圈因子,则T是Hamilton的;几乎正则非平衡3部竞赛图T,如果r≥18,r≠19,并且T有一个圈因子,则T是Hamilton的。 第二章研究了图的Ramsey数方面的问题。我们证明了Ramsey数r（k1,k2,…,km）,若ki=2,则r(k1,k2,…,ki-1,ki,ki+1,…,kn)=r(k1,k2,…,ki-1,ki+1,…,kn);若ki=3,则非平凡的Ramsey数r(k1,k2,…,ki-1,ki+1,…,kn)<r(k1,k2,…,ki-1,ki,ki+1,…,kn)。 第三章讨论了著名的平面图的“四色猜想”问题。我们证明了对于平图G,如果它的任意k个顶点的生成子图G′都有δ（G′）≤4则G是4-可着色的。在第二节中,我们指出了颜宪邦,屈姿朴在其《四色定理论证》一文中忽视的一个问题,此问题若无法解决,将会导致其证明方法失效。

论文目录

• 摘要
• Abstract
• 前言
• 第一章 Hamilton图
• 1.1 预备知识
• 1.2 Hamilton图的一个充分条件
• 1.3 一类度极大的非Hamilton简单平衡二部图
• 1.4 几乎正则多部竞赛图的Hamilton性
• 第二章 Ramsey数
• 2.1 预备知识
• 1，k₂…，k_n）的不等式性质'>2.2 Ramsey数r（k₁，k₂…，k_n）的不等式性质
• 第三章 四色问题
• 3.1 关于四色问题一些探讨
• 3.2 关于《四色定理论证》的质疑
• 参考文献
• 致谢
• 附录
• 承诺