英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料
章节 2
强边染色猜想
2.1介绍与历史
1985年，在布拉格举行的数学家会议上，P.Erdouml;s和J.Nescaron;etřil提出了下列问题（参见[12]和[13]）。
问题2.1 寻找最小的t(k)，使得如果满足△(G)=k，那么有schi;acute;(G)le;t(k)。
对于任何最大度为△的图G，schi;acute;(G)le;2△2-2△ 1，这个结论是微不足道的，这意味着t(k)le;2k2-2k 1。另一方面，Erdouml;s和Nescaron;etřil给出了下面猜想，其中图Gk
的最大度为k，则有：
schi;acute;(G)le;5k2/4 ，k是偶数
schi;acute;(G)le;5k2/4-k/2 1/4 ，k是奇数
这个例子展示了t(k)ge;schi;acute;(G)。对于k为偶数的情况，这个例子可以通过用k/2大小的独立集合替换每一个5-圈上的结点来获得，如果5-圈上2个对应结点相邻，则连接它们（用独立集合来替换图中结点的操作称之为顶点相乘法，此时得到的图我们记作C5k/2）。对于k为奇数的情况，这个例子可以通过用(k 1)/2大小的独立集合替换每一个5-圈上的结点来获得，其他部分可以通过用(k-1)/2大小的独立集合替换每一个5-圈上的结点来获得（如图2.1所示）。在每一种情况下，显而易见地，我们能够看到对于图G不存在两种不同大小的匹配，因此每条边的颜色都是明确的。
猜想2.1（强边染色猜想）对于任意最大度为△的图G，schi;acute;(G)le;f(△)，其中f(△)的定义如下：
f(△)le;5△2/4 ，k是偶数
f(△)le;5△2/4-△/2 1/4 ，k是奇数
在1989年，R.J.Faudree et al.[14]提出了关于二部图索引的强边染色猜想。完整的二部图K△,△展示了如下的猜想，如果猜想是正确的，那便是最好的可能性了。
猜想2.2（二部图强边染色猜想）对于任意最大度为△的二部图G，有schi;acute;(G)le;△2。
R.Brualdi和J.Quinn[8]将上述猜想推广如下：
猜想2.3（广义二部图强边染色猜想）对于任意以X,Y为两部分的二部图G，X部分与Y部分的最大度分别为alpha;与beta;，则有：schi;acute;(G)le;alpha;beta;。
值得注意的是，强边染色这个概念是由R.J.Faudree定义的，并且在P.Erdouml;s和J.Nescaron;etřil提出猜想之前就有了文献J.L.Jolivent[16,17]。他们研究了立体图强边色数。
本章我们对已知的相关问题与相关猜想作了概要性论述。在2.2节我们将着重介绍M.Molloy and B.Reed所提出的强边染色数。2.3节包含了强边染色猜想所隐含猜想的一些总结。在2.4节你将看到关于有最小度的图的一些强边染色结果。2.5节包含了一些特殊图的强边染色的结果。一些与强边染色算法问题相关的结果会在第2.6节提及。最后，在2.7节，我们列举了一些与强边染色相关的猜想。
2.2 一般情况的上界
Horak, Qing.和Trotter（参见[22,23]）评论说：对于某些ε＞0，有schi;acute;(G)le;(2-ε)△2，这是一个非常难证明的问题。在文献[35]中，M.Molloy and B.Reed通过下面的定理解决了这个问题。这是唯一已知的关于强边染色数的一般上界。
定理2.1 如果图G的最大度为△，并且△足够大，那么schi;acute;(G)le;1.998△2。
这个定理的证明包含两部分。在第一部分里，证明了对任意的图G，平方线性图是1/34-稀疏的等价于对L(G)2的任意结点v，至多存在(1-1/36)(△(L(G)2)/2)条边以v为端点。在第二部分里，证明了对任意delta;＞0，存在一个gamma;＞0使得如果图H是delta;-稀疏的，则它的强边染色数至多为(1-Upsilon;)△(H)。这一部分的证明是基于概率统计方法的，所用的方法是与随机过程类似的随机颜色迭代，这种方法我们将在第4章中使用（关于这部分证明的思路我们将在3.4.2节提及）。事实上，第四章的相关证明结果正是由以上定理的证明过程所推动的。
2.3 一些猜想结果
强边染色猜想包含了以下两个猜想。这里sm(G)代表图G的最大诱导匹配的大小，am(G)代表图G的最大反匹配的大小。一个反匹配指的是任何两个元素距离至多为2的边集合。显然可知，sm(G)和am(G)分别指的是最大独立集的大小与最大平方线性图的大小。
猜想2.4 对于任何图G，|E(G)|le;f(△)sm(G)，其中f是由2.1方程式所定义的函数。
猜想2.5 对于任何图G，am(G)le;f(△)，其中f是由2.1方程式所定义的函数。
2.4的一个特例可以根据2K2-自由图作出。如果一个连通图不包含由2K2的同构诱导子图，则称该连通图为2K2-自由图。2K2-自由图这一类图有非常多的有趣的性质（例如可以参考[51]或[11]）。这同时也产生了大量的关于图论理论的应用。例如说完美图形猜想以及强边染色数猜想等等。
当sm(G)=1时，猜想2.4能够被下列猜想准确表述。
猜想2.6（Bermond猜想）对于每个最大度为△的2K2-自由图，其边数至多为f(△)，其中f是由2.1方程式所定义的函数。
上面这个猜想由Erdouml;s和Nescaron;etřil在文献[13]中提出。在此之前，在1983年，Bermond et al.在文献[5]中也提出了这个猜想。他们之所以提出了这个猜想是由人们研究总线互联网络设计的问题所推动的（参见[5,4,6]）。这个问题具体来说是关于多处理器系统中所需处理器的最大数量的。处理器通过总线通讯，每个处理器都在两条总线上，最多d个进程可以同时共享一条总线。这个问题的目标是找到我们能够设计的最大处理器数量。我们可以为其设计一个这样的总线互联通信网络，以便每两个处理器P1和P2，要么处理器P1和P2可以通过一条总线直接交流，要么存在另一个处理器P，使得P与P1，P与P2同时可以通过一条总线直接交流。我们不难发现，在这样的系统中处理器的最大数量问题和最大度为d的2K2-自由图的最大边数问题是等价的。
在文献[5]中提到了D.J.Kleitman曾经证明了Bermond猜想对△是偶数的情况成立。但明显地，他的证明过程从未发表过。第一个公开发表了证明Bermond猜想过程的人是Chung et al.[10]。同时他也证明了通过顶点相乘法可以从5-圈中得到有唯一极值的2K2-自由图（如图2.1所示）。对于正则图的情况，这一事实还有另外一种证明方法，这些结果以及与之相关的问题都可以在文献[38]里找到。同时，关于强匹配的一些大类的充分性与必要性的证明可以在文献[31]里找到。
以下是Bermond猜想的一个推论。
定理2.2 对于任何最大度为△的图G，schi;acute;(G)le;2△(△-1)。
证：根据Brook定理，对于任意的图G，都有：
schi;acute;(G)＝chi;(L(G)2)le;△(L(G)2)＝2△(△-1)。
除非L(G)2是一个完全图或者奇数圈。容易验证平方图不可能是长度大于3的奇数圈。如果L(G)2是一个完全图，这意味着图G是一个2K2-自由图。但此时，根据Bermond的理论，图G的边数至多为f(△)，因此schi;acute;(G)le;|E(G)|le;f(△)le;2△(△-1)。
猜想2.5依然未被证明，下面这个猜想的一个较弱情况被Faudree et al.在文献[15]中证明。
定理2.3 存在一个常数ε＞0，使得am(G)le;(2-ε)△2。
值得注意的是，上面的这个定理依然包括在Mol1oy and Reed的结果中（定理2.1）。
定理2.4 对于任何二部图G，am(G)le;△2。
这个定理的证明非常短并且也很简单。他们同时也在文献[14]中证明了任何最大度为△的二部(k 1)K2-自由图至多有f(△)条边。这个理论包含了下面的定理。
定理2.5 对于任何二部图G，|E(G)|le;△2sm(G)。
他们还证明了唯一的极值图拥有形式：mC8△/2cup;nK△,△，其中满足2m n=k。
2.4 拥有最小度的图
schi;acute;(G)le;2△2-2△ 1的不平等性表明了强边染色猜想仅仅对△le;2成立。因此，首先应该考虑的非平凡情形便是△＝3。L.Andersen[3]和P.Horak et al.[22]分别独立地解决了这个问题，他们证明了以下定理。
定理2.6 若图G的最大度△le;3，则schi;acute;(G)le;10。
在文献[3]中，他们还证明了对于任意最大度△le;3的图G，存在一种线性时间复杂度的算法可以用来寻找只需要用10种颜色的强边染色方案。
对△＝4，根据强边染色猜想，每一个图都应该有一个使用20种颜色的强边染色方案。根据定理2.2，我们可以得知：每一个图都有一个使用24种颜色的强边染色方案。这个上界被Horaacute;k在文献[21]中改进，并提出了下面的定理。
定理2.7 若图G的最大度△le;4，则schi;acute;(G)le;23。
这是关于△＝4唯一已知的结果。对于△ge;5的情况，这个问题还没有被解决。
对于二部图的情形，△＝3的情况被A.Steger和M.Yu在文献[49]中解决。
定理2.8 若二部图G的最大度△le;3，则schi;acute;(G)le;9。
猜想2.2中△ge;4的情形目前还未被证明。对于猜想2.3，除了上述定理外，唯一已知的结果（在alpha;=beta;=3的情况下解决了这个猜想）如下列所示。这个结果的证明在文献[8]中可以看到。
定理2.9 设图G是以X，Y为两部分的二部图，且图G没有4圈。若X的结点最大度为2，Y的结点最大度为△，则schi;acute;(G)le;2△。
事实上，在文献[8]中猜想了可以将上述定理的2△替换为△ 2。这个猜想目前还未被证明，并且看上去似乎非常难证明。
2.5 几类特殊的图
很多类图的强边染色猜想都已经被证明，在这一节里，我们列举一些这种类型的图。
最大度为4的平面图可19-强边染色
Ying Wang a , Wai Chee Shiu b, * , Weifan Wang a , Min Chen a
aDepartment of Mathematics, Zhejiang Normal University, Jinhua 321004, China
bDepartment of Mathematics, Hong Kong Baptist University, 224 Waterloo Road, Kowloon Tong, Hong Kong, China
1.介绍
k-强边染色是两条距离至多为2的边染不同的颜色的特殊k-边染色。强边染色需要用到的最少颜色数，记为chi;Sacute;(G)。强边染色的概念在Fouquet和Jolivet发表的文献[6]中开始被采用。在1985年，Erdouml;s和Nescaron;etřil提出了下面的猜想：
猜想1.1（Erdouml;s和Nescaron;etřil[3,4]）.forall;G，有：
chi;Sacute;(G)le;5/4△2 ，△是偶数
chi;Sacute;(G)le;5/4△2-1/2△ 1/4 ，△是奇数
Anderen[1]和Horaacute;k et al.[7]证明了这个猜想对△=3成立。
对△ge;3的平面图，Faudree et al.证明了下列定理：
定理1.1(Faudree
全文共15827字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[843]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
