中文摘要：

拉姆塞理论在很多领域都有应用，如信息论和计算机科学等。图的拉姆塞数研究是拉姆塞理论的一个主要研究方向，它对网络设计中通信设施数量的选择以及通讯频道Shannon容量的确定有重要意义。它是NP困难问题，研究它对解决一般NP困难问题有意义。到目前为止，只有很有限的一些图簇的拉姆塞数得到了精确值，其成果主要集中在对两色拉姆塞数的研究。但实际应用中遇到的可能是多色拉姆塞数。本课题着重研究圈的多色拉姆塞数以及相关极图问题；研制出较好的计算圈的多色拉姆塞数的算法、计算圈的多色拉姆塞数下界的算法以及构造相关极图的算法。主要目标是探索出一条求解圈的多色拉姆塞数问题的有效途径，为圈的拉姆塞数的实际应用提供更坚实的理论基础，也为其它图簇多色拉姆塞数的求解提供借鉴。　　在图的多色拉姆塞数研究领域，申请者已经取得了一些研究成果。本项目的研究，将有助于我们在该领域取得更大的突破。

结论摘要：

本项目主要对圈的多色拉姆塞数及极图问题进行了研究，取得了一些研究成果。首先研究了特定的非完全图在边着色算法中的应用。在对多色拉姆塞数的研究中，证明了一些比较规范的非完全图如二部图或多部图的一些性质，并将其运用到多色拉姆塞数的求解中。利用该成果确定了R3(C8)和R(K4-e, K4-e, C4)的准确值，这些特殊子图的应用可使算法的执行效率提高十倍以上。在此基础上对二部拉姆塞数进行了深入研究，证明了b(C2m; K2,2)和b(C2m; C6)的准确值，并给出了b(C2m; C2n)的下界。发表期刊论文2篇，国际会议论文1篇，其中1篇期刊论文已被SCI检索。这项研究成果不仅有助于求解多色拉姆塞数R(G, C6, C4)、R(G, C6, C6) 和R4(C6)，而且也有助于求解其他相关多色拉姆塞数。其次，研究了圈的4色拉姆塞数R(Cm, Cn, Ck, C6)，其中m、n和k等于4或6。利用拼图法确定了R(C6, C4, C4, C4) = 19，关于该成果的论文已被SCI刊源期刊录用。此外还确定了18 ≤ R(C6, C6, C4, C4) ≤ 19、18 ≤ R(C6, C6, C6, C4) ≤ 19和18 ≤ R4(C6) ≤ 19。在对拼接的图的补图2着色时充分研究了边着色顺序与着色效率的关系，在着色前重新给顶点合理标号以提高算法的执行效率。第三，研究了不含偶圈的极图构造算法。设计了不包含偶圈的分布式极图构造算法，计算出顶点数不超过28且不含六边形的极图。计算结果表明，该分布式算法的平均执行效率达到了75.48%，最高值则达到91.41%。关于该成果的论文已被EI刊源期刊录用。第四，研究了围长为9和10的极图，确定了当22 ≤ n ≤ 30时ex(n;{C3,C4,…,C8})的准确值，并给出当31 ≤ n ≤ 57时ex(n;{C3,C4,…,C8})的下界，关于该研究成果的论文已投稿到Utilitas Mathematica(SCI刊源期刊)。还确定了当26 ≤ n ≤ 33时ex(n;{C3,C4,…,C9})的准确值，并给出当34 ≤ n ≤ 69时ex(n;{C3,C4,…,C9})的下界。