论文部分内容阅读
图G的正常k-全染色是指用k种颜色给V(G)∪E(G)中的元素进行染色,使得任意两个相邻的或相关联的元素均染不同的颜色。使得图G有正常的k-全染色的最小正整数k称为G的全色数,记为x"(G)。类似的,我们可以定义图G的正常点染色和正常边染色,对应的色数分别称为点色数和边色数,分别记为x(G)与x(G)。荫度的概念可以看作是图的一种染色(不一定是正常的),其中每个色类的导出子图是一个森林。本文研究了几种不同的荫度概念:图的线性荫度、线性k-荫度、k-星荫度、全荫度、列表全荫度和强均匀点荫度。主要内容概括如下: (1)图的线性荫度。一个线性森林是指每个连通分支都是路的森林。图G的线性荫度是指使得G可以分解成m个线性森林的最小正整数m,用la(G)表示。本文确定了完全图与路、完全图与圈,以及两个完全图的笛卡尔积图的线性荫度。 (2)图的线性k-荫度。一个线性k-森林是指每个连通分支都是长度不超过k的路的森林。图G的线性k-荫度是指使得G可以分解成m个线性k-森林的最小正整数m,用lak(G)表示。本文首先研究了两个圈的笛卡尔积图的线性2-荫度,得到了确切的数值。此外,本文研究了几类特殊的平面图,分别给出了这些平面图的线性2-荫度的上界。 (3)图的k-星荫度。一个星是指至多一个顶点的度大于1的树。一个k-星森林是指所有分支都是顶点数不超过k+1的星的森林。使得图G可以分解成m个k-星森林的最小正整数m,称为图G的k-星荫度,用sak(G)表示。本文讨论了最大度不超过3的图和树的k-星荫度的上下界,并给出了两个相关的算法。 (4)图的全荫度和列表全荫度。在图G的一个k-全染色f(不一定是正常的)中,若每个色类的元素在全图中的导出子图是一个森林,则称f是图G的一个无圈k-全染色。使得图G有一个无圈k-全染色的最小正整数k称为图G的全荫度,记为ρ"(G)。对于图G的每个元素x,如果我们都给它指定一个颜色集合L(x),那么我们称L为G的一个列表。设L是G的一个给定的列表,如果存在G的一个无圈全染色f,满足对任意的元素x∈V(G)∪E(G)都有f(x)∈L(x),则称f是G的一个无圈列表全染色。若对于满足|L(x)|≥k的任意可能的列表L,G都有一个无圈列表全染色,则称G是无圈k-全可选的。使得图G是无圈k-全可选的最小正整数k称为图G的列表全荫度,记为ρ"l(G)。这两个概念是Hetherington提出的。此外,他还提出了关于全荫度的猜想:对任何简单图G,均有「△(G)+1/2(])≤ρ"(G)≤「△(G)+2/2(」)。本文完全确定了完全图Kn和完全二部图Kn,n的全荫度,证明以上猜想对这两类图是成立的。对于Halin图,我们给出了其列表全荫度的上界。本文还研究了平面图的全荫度,证明了对于△(G)≥13的平面图和△(G)≥7且不含4-圈的平面图,全荫度猜想都是成立的。 (5)图的强均匀点荫度。设f是图G的顶点的一个t-染色,若每个色类的导出子图的每个分支都是最大度不超过k的树,则称f为图G的一个(t,k)-树染色。设f为图G的一个(t,k)-树染色且任何两种不同颜色所染的顶点数最多相差1,则称f为图G的一个均匀(t,k)-树染色。使得对所有的t≥t,图G都具有均匀(t,k)-树染色的最小正整数t,称作强均匀点k-荫度,记作va≡k(G)。吴建良等人首先提出了这个概念,并且猜想:对任何平面图G,均有va≡∞(G)=O(1)。在本文中,我们首先研究了完全二部图Kn,n的强均匀点1-荫度,得到了一些相关的结果。其次,我们研究了两类特殊的平面图,分别得到了强均匀点∞-荫度的上界,从而证明了吴建良的猜想对这两类平面图是成立的。