关于图的一些荫度问题的研究

发布时间：2018-06-02 01:47

本文选题：线性荫度 + 线性k-荫度　；参考：《东南大学》2015年博士论文

【摘要】：图G的正常k-全染色是指用k种颜色给V(G)∪ E(G)中的元素进行染色,使得任意两个相邻的或相关联的元素均染不同的颜色。使得图G有正常的k-全染色的最小正整数k称为G的全色数,记为χ"(G)。类似的,我们可以定义图G的正常点染色和正常边染色,对应的色数分别称为点色数和边色数,分别记为χ(G)与χ'(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,均有本文完全确定了完全图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-荫度,记作vak≡(G)。吴建良等人首先提出了这个概念,并且猜想：对任何平面图G,均有va∞≡(G)=O(1)。在本文中,我们首先研究了完全二部图Kn,n的强均匀点1-荫度,得到了一些相关的结果。其次,我们研究了两类特殊的平面图,分别得到了强均匀点∞-荫度的上界,从而证明了吴建良的猜想对这两类平面图是成立的。
[Abstract]:In this paper , we study several different shade concepts : the linear shade , the linear k - shade , k - star shade , the shade , the total shade of the list and the shade of the strong uniform . Let G be a given list of G . Let G be a given list of G . If we all assign a color set L ( x ) to any possible list L , G of graph G , we call that G is a non - circle k - total coloring . If there is a non - circle full dyeing f of G , it is called G . If there is a non - circle full dyeing f of G , we call f to be one ( t , k ) - tree dyeing of G . Let f be a graph G ( t , k ) - tree dyeing . Let f be a uniform ( t , k ) - tree dyeing of G . If f is a graph G , we call f a uniform ( t , k ) - tree dyeing . The minimum positive integer , t , called strong uniform point k - shade , called strong uniform point k - shade , is known as vak ident ( G ) .
【学位授予单位】：东南大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O157.5

【相似文献】