图的［r，s，t］-着色

论文摘要

图的着色是经典的图论问题,图的着色理论在离散数学中占有很重要的地位,并且在组合分析和实际生活中有着广泛的应用。近年来多种着色问题被相继提出并加以发展和应用。2007年,A . Kemnitz和M M arangio提出了图的[ r , s , t ]-着色。由于[ r , s , t ]-着色中有三个参数r ,s和t,研究起来有相当难度,所以目前对[ r , s , t ]-着色研究的文献非常少。本文分别就一般图中的二部图（星、路）、圈、扇图、轮图的[ r , s , t ]-着色进行讨论,并将一般图的[ r , s , t ]-着色推广到超图上。首先,综述了一般图的点着色、边着色、全着色和L （ p , q ）-标号的概念、研究现状和全着色及L （ p , q ）-标号的研究方法。图的[ r , s , t ]-着色是点着色、边着色和全着色的推广,且与L （ p , q ）-标号的定义有一些类似之处,所以这些问题的研究方法可直接应用于图的[ r , s , t ]-着色的研究。其次,由于特殊图有着一些特殊的结构和性质,所以图论的很多研究课题都可以从它们进行入手,以便找到更一般的规律。当然,对着色问题的研究也不例外。于是,在第三章中对二部图（星、路）、圈、扇图、轮图等一些特殊图的[ r , s , t ]-色数进行研究,为以后进一步讨论更一般的情况作一些铺垫。对特殊图的[ r , s , t ]-色数的研究,首先证明了一般的二部图当r , s ,t满足一定条件时的[ r , s , t ]-色数,接着对特殊的二部图——星和路具体讨论当它们满足一定条件时的[ r , s , t ]-色数,然后讨论当r , s ,t满足一定条件时奇圈和偶圈的[ r , s , t ]-色数,最后研究了扇图和轮图的[ r , s , t ]-色数。因为当r , s ,t取不同的值时有可能产生不同的[ r , s , t ]-色数,所以在讨论图的[ r , s , t ]-着色时有必要先对变量r , s ,t取值进行一些限制。最后,超图作为一般图的推广,同样可以把着色理论推广到超图上,于是就产生了超图的着色。关于超图的着色的内容也非常丰富,在第四章中,首先综述了一些超图着色概念及研究现状,然后利用一般图[ r , s , t ]-着色定义的方法,相应地把它推广到超图上,于是就提出了超图的[ r , s , t ]-着色,显然它是超图的强点着色、强边着色和强全着色的推广。关于超图的[ r , s , t ]-着色,首先得到它的一些性质,如定理4.2.3,定理4.2.4;然后证明了当min{r , s , t } = 0时超图的[ r , s , t ]-色数,如定理4.2.6-定理4.2.9;最后证明了当r和s满足一定条件时的χr ,1,1（ H）和χ1 , s ,1（ H）,并给出了χ1 ,1, t （ H）的上下界,详见定理4.2.10-定理4.2.12。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 着色问题的提出
• 1.2 常用术语
• 1.3 本文的研究目的和研究内容
• 1.3.1 研究目的
• 1.3.2 研究内容
• 2 一般图着色的概念及研究现状
• 2.1 点着色（Vertex Coloring ）
• 2.2 边着色（Edge Coloring ）
• 2.3 全着色（Total Coloring ）
• 2.4 L （ p , q ） - 标号（L （ p , q ）- labeling ）
• 2.5 本章小结
• 3 一些特殊图的[r , s , t ] - 色数
• 3.1 一般图的[ r, s , t ] -着色的概念及研究现状
• 3.2 二部图的[r , s , t ] - 色数
• 3.3 圈、扇图、轮图的[r , s , t ] - 色数
• 3.4 本章小结
• 4 超图的[r , s , t ] - 着色
• 4.1 超图着色的概念及研究现状
• 4.2 超图的[r , s, t ] - 着色
• 4.3 本章小结
• 5 结论与展望
• 5.1 主要结论
• 5.2 研究展望
• 致谢
• 参考文献
• 附录