论文部分内容阅读
1736年,瑞士数学家Euler在他的论文中讨论了哥尼斯堡七桥问题,由此诞生了一个全新的数学分支-图论。自从四色猜想被提出之后,图的染色问题就成为了图论的一个很重要的研究课题。图的染色理论在计算机理论、组合最优化、信息化科学和网络设计等方面均有着很重要的应用。图的染色理论有很多分支,如边染色、点染色、面染色和全染色等。其中研究最多,结果也较完善的就是图的边染色。本文旨在讨论图的一种比较特殊的边染色-强边染色。本文主要由五个章节组成,主要内容如下: 在第一章,我们首先给出本文用到的基本概念和记号,接着介绍图的强边染色的研究背景和研究现状,最后给出了本文的主要结果。 在第二章,我们着重研究稀疏图的强边染色问题。Hocquard等人最早是研究了最大度小于或等于3(Subcubic graphs)的稀疏图的强边染色。最近,Bensmail等人研究了最大度为4的稀疏图的强边染色,他们证明了最大度为4并且最大平均度分别小于16/5,10/3,17/5,18/5,19/5的图分别可以用16,17,18,19,20种颜色来强边染色。我们改进了他们的结果,证明了最大度为4并且最大平均度分别小于61/18,7/2,18/5,15/4,51/13的图分别可以用16,17,18,19,20种颜色来强边染色。在这一章的第二部分,我们证明了最大度为4并且最大平均度分别小于8/3,14/5的图分别可以用10,11种颜色来强边染色,并且给出两个图说明这两个最大平均度是接近最优的。 在第三章,我们证明了最大度为Δ(Δ≥6)并且最大平均度小于14/5的图可以用3Δ-1种颜色来强边染色。作为这一结果的一个结论,我们得到最大度为Δ(Δ≥6)并且围长g≥7的平面图可以用3Δ-1种颜色来强边染色,从而改进了Wang的结果:所有最大度为Δ≥6并且围长g≥7的平面图可以用3Δ种颜色来强边染色。 在第四章,我们首先集中精力研究伪Halin图的强边染色问题。伪Halin图是Halin图的一般推广。对Halin图的强边染色的研究,最早是Shiu等人,他们证明了Cubic Halin图强边色数至多是9。最近,Hu等人给出了Halin图的强边染色数的一个上界:每个Δ≥4的Halin图的强边染色数最多是2Δ+1。这一章我们证明了:每个Δ≥4的伪Halin图的强边色数最多是3Δ-2。需要说明的是,这个上界是接近最好可能的界,因为我们找到一个伪Halin图,它的强边色数刚好等于3Δ-3。在这一章的最后,我们将主要探讨K2,3-minor free图的强边色数问题。我们将证明:每个非空K2,3-minor free图的强边色数最多是4Δ-6,并且得到这个界是最好的,因为存在一个非空K2,3-minor free图的强边色数刚好为4Δ-6。 第五章作为本文的结束部分,我们提出了可以进一步考虑的研究问题。