图%5br%2cs%2ct%5d-着色

《图%5br%2cs%2ct%5d-着色》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、On[,,]rstColoringofGraphAThesisSubmittedtoChongqingUniversityinPartialFulfillmentoftheRequirementfortheDegreeofMasterofSciencebyZhangXinjunSupervisor:Prof.GongQuMajor:ComputationalMathematicsCollegeofMathematicsandPhysicsofChongqingUniversity,Chongqing,ChinaApril,2008重庆大学硕

2、士学位论文中文摘要摘要图的着色是经典的图论问题，图的着色理论在离散数学中占有很重要的地位，并且在组合分析和实际生活中有着广泛的应用。近年来多种着色问题被相继提出并加以发展和应用。2007年，AKemnitz.和MMarangio提出了图的[,,]rst着色。由于[,,]rst着色中有三个参数rst,和，研究起来有相当难度，所以目前对[,,]rst着色研究的文献非常少。本文分别就一般图中的二部图(星、路)、圈、扇图、轮图的[,,]rst着色进行讨论，并将一般图的[,,]rst着色推广到超图上。首先，综述了一般图的点着色、边着色、全着色

3、和Lpq(,)标号的概念、研究现状和全着色及Lpq(,)标号的研究方法。图的[,,]rst着色是点着色、边着色和全着色的推广，且与Lpq(,)标号的定义有一些类似之处，所以这些问题的研究方法可直接应用于图的[,,]rst着色的研究。其次，由于特殊图有着一些特殊的结构和性质，所以图论的很多研究课题都可以从它们进行入手，以便找到更一般的规律。当然，对着色问题的研究也不例外。于是，在第三章中对二部图（星、路）、圈、扇图、轮图等一些特殊图的[,,]rst色数进行研究，为以后进一步讨论更一般的情况作一些铺垫。对特殊图的[,,]rst色数的

4、研究，首先证明了一般的二部图当rst,,满足一定条件时的[,,]rst色数，接着对特殊的二部图——星和路具体讨论当它们满足一定条件时的[,,]rst色数，然后讨论当rst,,满足一定条件时奇圈和偶圈的[,,]rst色数，最后研究了扇图和轮图的[,,]rst色数。因为当rst,,取不同的值时有可能产生不同的[,,]rst色数，所以在讨论图的[,,]rst着色时有必要先对变量rst,,取值进行一些限制。最后，超图作为一般图的推广，同样可以把着色理论推广到超图上，于是就产生了超图的着色。关于超图的着色的内容也非常丰富，在第四章中，首先综

5、述了一些超图着色概念及研究现状，然后利用一般图[,,]rst着色定义的方法，相应地把它推广到超图上，于是就提出了超图的[,,]rst着色,显然它是超图的强点着色、强边着色和强全着色的推广。关于超图的[,,]rst着色，首先得到它的一些性质，如定理4.2.3，定理4.2.4；然后证明了当min{,,}0rst时超图的[,,]rst色数，如定理4.2.6－定理4.2.9；最后证明了当r和s满足一定条件时的()H和r,1,1()H，并给出了()H的上下界，详见定理4.2.10－定理4.2.12。1,,1s1,1,t关键词：图，超图，

6、[,,]rst着色，[,,]rst色数I重庆大学硕士学位论文英文摘要ABSTRACTGraphcoloringbelongstoclassicalgraphtheoreticalproblems.Graphcoloringth-eoryisveryimportantindiscretemathematics.Inthecombinatorialmathematicsandourliving，thecoloringproblemhasabigapplication.Manyscholarsinthisfieldpr-esentedmanyc

7、oloringproblemsinrecentyears.A.KemnitzandM.Marangioputforwardthe[r,s,t]-coloringin2007.Sincetherearethreeparametersinthe[r,s,t]-colo-ring,itisdifficulttostudyandtheresearchdocumentaboutitisfew.Thispaperstudiesthe[r,s,t]-chromaticnumberofthebipartitegraph,circle,fanandwheel,

8、respectively,andextendthe[r,s,t]-coloringtothehypergraph.Firstly,thispaperpresents