论文部分内容阅读
图的着色是经典的图论问题,图的着色理论在离散数学中占有很重要的地位,并且在组合分析和实际生活中有着广泛的应用。近年来多种着色问题被相继提出并加以发展和应用。2007年,.A Kemnitz和M Marangio提出了图的rst-着色。由于rst-着色中有三个参数,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{,,}0r s t=时超图的[,,]r s t-色数,如定理4.2.6-定理4.2.9;最后证明了当r和s满足一定条件时的,1,1() r Hc和1,,1()s Hc,并给出了1,1,()t Hc的上下界,详见定理4.2.10-定理4.2.12。