论文部分内容阅读
图的着色问题一直是图论研究中的重要问题之一,有着重要的理论意义和实用价值。近年来,图的着色研究非常活跃,产生了许多新的着色问题和新的研究方法,也得到了一系列漂亮的结果。继图的点着色、边着色和全着色之后,2007年A.Kemnitz和M.Marangio又提出了图的[r,s,t]-着色的概念,它是经典点着色、边着色和全着色的推广,具有非常广泛的应用。本文主要研究了一些特殊图的[r,s,t]-着色问题。 本文首先对涉及到的一些基本概念、研究背景及研究目的作介绍,综述了一般图的点着色、边着色和全着色的概念及研究现状,这些研究结果和方法可直接应用于图的[,,]rst-着色研究中。同时,引入A.Kemnitz和M.Marangio提出的[r,s,t]-着色的概念,并对当前的研究现状进行综述。A.Kemnitz和M.Marangio给出了一般图的[r,s,t]-色数的界及一些相关性质,同时讨论了n阶完全图的[r,s,t]-色数。本文根据A.Kemnitz给出的[r,s,t]-色数一些性质,得到几个平行的结论。 接着,由于特殊图有着一些特殊的结构和性质,所以图论的很多研究课题都可以从它们开始,以便找到更一般的规律。图的着色问题的研究也不例外。于是,在第三章中对特殊图风车图K、图)(n3D、齿轮图nW~的[r,s,t]-色数进行研究,首,m4先给出了它们的点色数、边色数和全色数,再根据一般图的[r,s,t]-色数的界及一些性质,讨论当,,rst满足一定条件时这些特殊图的[r,s,t]-色数。 最后,将两个点不相交的图的联图进行研究也是图论研究的一个常用方法,在第四章中研究了空图与圈、圈与圈这两类联图的[r,s,t]-色数。先给出了这两类联图的点色数和边色数,得到空图与圈联图当圈的阶比空图的阶大一时,是第二类图,其它情况是第一类图。圈与圈的联图当两圈的阶数仅差一时是第二类图,其它情况是第一类图。由此,再根据一般图的[r,s,t]-色数的界及一些性质,讨论当,,rst满足一定条件时这两类联图的[r,s,t]-色数。