图的几类染色问题以及超图中的彩色匹配

发布时间：2020-05-07 11:06

【摘要】：图染色理论和极值图论是图论中非常重要的两个研究课题,在计算机科学、信息安全以及模式匹配等领域有着广泛的应用。在本文中,我们主要讨论了以下几类图染色问题以及3-一致超图中彩色匹配的Turan类问题。给定一个图G =(V,E)和图G的一个正常全染色Φ:V ∪ E →{1,2,...,k}。以mΦ(v)表示点v及其关联边上颜色的和值,即mΦ(v)=Φ(v)+∑uv∈EΦ(uv),我们称mΦ(v)为点v在染色Φ下的导出颜色和。如果mΦ(u)≠mΦ(v)对图G中任意一条边uv都成立,则称正常全染色Φ为图G的一个邻和可区别全染色。使得图G存在一个邻和可区别全染色的最小整数k称为图G的邻和可区别全色数,记为χ"∑(G)。关于邻和可区别全染色,Pilsniak等人猜想对于任意至少包含两个点的连通图G,其邻和可区别全色数至多是△(G)+3。记col(G)为满足下面条件的最小整数k:存在图G的一个点排序,使得每个点至多有k—1个邻点位于该点之前。在本文中,我们考虑的是列表邻和可区别全染色,其相关概念的定义如下。令L = {Lx|x ∈ V ∪E}是一个列表集,如果存在一个邻和可区别全染色Φ:V∪E→∪x∈V ∪E Lx 满足对任意的x ∈ V ∪ E,都有Φ(x)∈Lx,则称Φ为在列表集L下的邻和可区别全染色。如果对于任意的列表集L= {Lx丨x ∈ V∪E},只要丨Lx丨≥ k对所有的x ∈ V∪E成立,都存在图G的一个在列表集L下的邻和可区别全染色,则称图G是k-邻和可区别全可选的。使得图G是k-邻和可区别全可选的最小整数k称为图G的邻和可区别全选择数,记为ch"∑(G)。在第二章,我们结合组合零点定理与图的一些结构性质对列表邻和可区别全染色进行了研究,并证明任意的图G都满足ch"∑(G)≤ △(G)+ 2col(G)—2,并且当图G不是森林且△(G)≥4时,图G满足ch"∑(G)≤ △(G)+ 2col(G)—3。另外,对于最大度为3的图G,我们还证明ch"∑(G)≤ 7,并且当mad(G)20/7时,ch"∑(G)≤6。假设Φ:E→{1,2,...,k}是图G的一个正常边染色。以CΦ(v)表示点v关联边上的颜色构成的集合,即CΦ(v)={Φ(uv| uv ∈E},我们称CΦ(v)为点v在染色Φ下的导出颜色集。如果图G中任何一条边uv都满足CΦ(≠ CΦ(v),则称正常边染色Φ是图G的一个邻点可区别边染色。使得图G存在一个邻点可区别边染色的最小整数k称为图G的邻点可区别边色数,记为χ'a(G)。这一概念是由Zhang等人于2002年提出的。他们猜想对任意至少包含6个点的连通图G,其邻点可区别边色数不超过△(G)+2。我们称一个图为正规图,如果该图不含孤立边。在第三章,我们结合组合零点定理和充放电技术研究了平面图的列表邻点可区别边染色,并证明任意的正规平面图G都满足其中ch'a(G)表示图G的邻点可区别边选择数。与邻和可区别全染色的定义类似,我们定义图G的邻和可区别边染色以及邻和可区别边色数χ'∑(G),其中点v在正常边染色Φ下的导出颜色和mΦ(v)定义为∑uv∈EΦ(uv)。不难看出,一个图G的邻和可区别边染色一定是该图的邻点可区别边染色,因此χ'a(G≤ χ'∑(G)。关于邻和可区别边染色,Flandrin等人猜想除长度为5的圈之外,任意的连通正规图G的邻和可区别边色数至多是△(G)+2。这一猜想推广了 Zhang等人提出的邻点可区别边染色猜想。在第三章,我们对平面图的列表邻和可区别边染色进行了研究,并证明任意的正规平面图G都满足其中ch'∑(G)是图G的邻和可区别边选择数。图G的一个正常边染色Φ称为图G的r-无圈边染色,如果图G中的每一个圈C都至少包含min{|C|,r}种颜色。使得图G存在一个r-无圈边染色的最小颜色数称为图G的r-无圈边色数,记为A'r(G)。在2005年,Greenhill等人证明对于r≥4,有A'r(d)=Θ(d「r/2」)成立,其中A'r(d):=max{A'r(G)| △(G)= d}。他们给出的A'r(d)的上界为「2 5r+4/6(r+2)」△「r/2」。在第四章,我们用熵压缩方法对r ≥ 4时的r-无圈边染色进行了研究,并证明任意图G的r-无圈边色数不超过2△+「r/2」+O(△r+1/3),并且当r是偶数时,任意图G的r-无圈边色数不超过△「r/2」+O(△r+1/3)。对于r是偶数的情况,我们给出的r-无圈边色数的上界是渐进最优的。另外,我们还研究了大围长图的r-无圈边色数,并证明任意围长至少是2r-1的图G都满足A'r(G)≤(9r-7)△ + 10r-12。以上这些结果都大大改进了之前的结果。假设H={H1,H2,...,Ht+1}是一族顶点集相同的k-一致超图,如果M是一个匹配且至多包含每个Hi(i ∈[t+1])中的一条边,则称M为H的一个彩色匹配。以exk(n,t)表示顶点个数为n且至多含有t条独立边(即两两互不相交的边)的k-一致超图所能具有的最大边数。确定exk(n,t)的值是一个非常重要的Turan类问题。在1965年,Erdos猜想exk(n,t)= max{(k(t+1)-1 k),(n k)-(n-t k)}。最近,Aharoni 和 Howard 考虑了彩色匹配的Turan类问题,并猜想如果每个Hi(i∈[t + 1])的顶点数为n且都至少包含exk(n,t)+ 1条边,则H含有一个大小为t+ 1的彩色匹配。在第五章,我们讨论了该猜想在k= 3时的情形,并证明当n ≥ 3.9t+ 10时,该猜想成立。
【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：O157.5

【参考文献】