标号染色论文-李瞳

导读:本文包含了标号染色论文开题报告文献综述及选题提纲参考文献，主要关键词:邻积可区别全染色,反魔幻标号,彩色匹配

标号染色论文文献综述

李瞳^[1]（2019）在《图的染色标号问题及超图中的彩色匹配》一文中研究指出图的染色理论和极值图论一直是图论研究领域中的重要分支,在组合最优化、计算机科学以及模式匹配等方面有着广泛的应用,因此长久以来备受关注。本文旨在讨论图的染色问题、标号问题以及超图中关于匹配的彩虹Turan问题。在本文中,除特殊声明外,我们所提到的图均为无向、有限、非空的简单图。给定一个图G,我们分别用V(G)、E(G)、△((G)、δ(G)和mad(G)(或简便起见,用V、E、△、δ和mad)来表示图的点集、边集、最大度、最小度和最大平均度。首先,我们研究了图的邻积可区别全染色问题。给定一个图G=(V,E),图G的一个正常[k]-全染色c是指图G的一个正常全染色c:V ∪ E{1,2,...,kk}。我们用p(v)表示所有与点v相关联的边的颜色及点v本身颜色的乘积,即p(v)=c(v)Пuv∈E(G)C(uv)。若对于图G中任意一条边uv,均有p(v)≠p(u)成立,则我们称染色c以乘积区分相邻点,并且称c为图G的一个邻积可区别全染色。使得图G存在一个邻积可区别全染色的最小整数kk,我们称之为邻积可区别全色数,记作x"П(G)。关于邻积可区别全染色,我们猜想对于包含至少两个点的连通图G,其邻积可区别全色数至多是△(G)+3。在第二章,我们证明了对于最大度至少为10的平面图,其邻积可区别全色数至多为max{△((G)+2,13};对于最大平均度小于3的图,其邻积可区别全色数至多为max{△({+2,7}。图的标号问题是一类特殊的图染色问题。在本文中,我们主要研究了图的反魔幻标号问题。图G的反魔幻标号是指从图G的边集E(GE到集合{1,2,...,|E(G)|}的一个双射,使得图中任意两个点的点和均不同,其中,点和是指该点的邻边标号之和。如果图G存在一个这样的反魔幻标号,那么我们就称图G是反魔幻的。1990年,Hartsfield和Ringel提出了这样一个猜想:除K2外所有的连通图均是反魔幻的。目前,该猜想仅被证明对于正则图、稠密图及部分特殊图类成立,即使是对于树,该猜想仍未被证实。受这一猜想的影响,Hefetz,Muutze和Schwartz等人在2010年开始研究有向图的反魔幻标号问题。有向图D的一个标号是指从D的边集A(D)(统一起见,我们将有向图中的弧仍称为是边)到集合{1,...,|A(D)|}的一个双射。如果D的标号可以使得图中任意两点的点和均不同,则称该标号是反魔幻的,其中,点和是指该点的入边标号之和减去该点的出边标号之和。若图G的一个定向DD有一个反魔幻标号,则称图G存在一个反魔幻定向。Hefetz等人提出猜想:任意连通图均存在反魔幻定向。目前,该猜想已被证明对于奇正则图、双正则二部图、稠密图及部分特殊图类是成立的。在第叁章,我们证明了该猜想对于偶正则图是成立的。给出一个n个点的kk-一致超图H,如果H没有大小为s+1的匹配,那么H中最多可以存在多少条边?这是Erdos在1965年提出的一个极值组合领域的重要问题。一般情况下,我们用exk(n,s)表示顶点个数为n且不含大小为s+1的匹配的kk-一致超图所能具有的最大边数。Erdos猜想该问题有两个极图结构:第一个是由k(+1)-1个点的团和n-k(-+1)+1个孤立点构成的超图;第二个是所有边均和一个固定的s个点的集合有交的超图,由此猜想exk(n,s)=max{(k(s+1)—1),-1),(n k)-(n-s k)}。那么,如果该超图H是正常染色的且H没有大小为s+1的彩色匹配,那么H中最多可以存在多少条边?显然,这一问题是上述Erdos所提问题的推广(Erdos所提问题对应于该问题中H是彩虹图的特殊情况)。我们用ex*k(n,S)表示顶点个数为n且不含大小为s+1的彩色匹配的正常染色k-一致超图所能具有的最大边数。我们猜想ex*k(n,s)= max{(k(s+1)-1k),(n k)-(n-s k)}。在第四章,我们证明了当n ≥ 7.6s时,该猜想对于3-一致超图是成立的。更进一步地,假设H= {H1,H2,...,Hs+1}是一族顶点集均为[n]的k-一致超图,如果我们可以从每个超图中各取出一条边,构成一个大小为s+1的匹配,那么每个超图的边数至少是多少?Aharoni和Howard考虑了这一问题并猜想边数应至少为max(k(s+1)-1 k),(n k)-(n-s k)}+1。我们同样推广了这一猜想,考虑了正常染色的s+1个一致超图构成的集族H,并猜想当每个超图的边数至少为max{(k(s+1)-1 k),(n k)-(n-s k)}+1时,我们可以找到H的一个大小为s+1的彩色匹配,此处的彩色匹配意味着每条边均是从不同超图中取出的点不交的边且颜色两两均不同。在第四章,我们证明了当n≥3k2S时该猜想成立。(本文来源于《山东大学》期刊2019-05-22）

朱俊蕾^[2]（2019）在《L(2,1)-标号和r-动态染色》一文中研究指出图的染色问题是图论研究中的重要问题和热点问题之一,标号问题是染色问题的推广,它起源于通讯问题中的信道频率分配问题.1991年,Roberts提出了给相近和非常相近的发射机分配不同的信道,并且非常相近的发射机接收的信道频率要至少相差两个单位.受这一问题的启发,Griggs和Yeh在1992年系统地提出了 L(2,1)-标号问题.这一概念后来被推广到了图的L(p,q)-标号问题.令p,g为正整数,图G的一个k-L(p,q)-标号是指映射f:V(G)→ {0,1,2,…,k},使得对任意的2个顶点u和,若d(u,v)=1,则有 |f(u)-f(v)|≥p,若d(u,v)=2,则有 |f(v)-f(v)|≥q.其最小的 k值称为图 G 的L(p,g)-标号数,记为λp,q(G).图的L(1,1)-标号等价于2-距离染色.2001年,Montgomery在他的博士论文中提出了动态染色.令k,r为正整数,[k]={1,2,..…,k},图G的一个r-动态染色是指一个正常k-顶点染色f,满足对任意的顶点v,都有|f(NG(v))|≥min{d_G(v),r}.其最小的k值称为图G的r-动态色数,记作(?)(G).特别地,当r=△(G)时,r-动态染色就是图的2-距离染色.本学位论文研究与信道频率分配相关的特殊图类的L(2,1)-标号问题和r-动态染色问题.第一章综述了国内外关于L(2,1)-标号问题和r-动态染色问题的研究现状.第二章围绕Griggs-Yeh猜想展开研究.1992年,Griggs和Yeh猜想:对最大度△ ≥ 2的图G,有λ2.1(G)≤△~2.结合权转移方法和零点定理,我们得到了不含某些特殊短圈的平面图的列表L(2,1)-标号数的上界和平面图在最大度和围长限制条件下的列表L(2,1)-标号数的上界.论文的后面叁章围绕赖虹建等人提出的关于平面图r-动态染色的猜想展开研究.2014年,类似Wegner猜想,赖虹建等人提出:对平面图G,若1 ≤ r ≤ 2,则(?)(G)≤r+3;若 3 ≤ r ≤7,则 Xrd(G)≤ r+5;若 r ≥ 8,则 (?)(G)≤[3r/2]+1.第叁章研究了不含特殊短圈的平面图的列表2-距离染色数(即列表△-动态染色数)和平面图的2-距离染色数(即△-动态染色数),得到了:(1)不含4-圈和6-圈的平面图的列表2-距离染色数的上界;(2)平面图G的2-距离染色数的上界,这一结果改进了目前关于最大度△≤7的平面图的2-距离染色数的最好上界.第四章研究了围长至少为5和围长至少为7的平面图的(列表)r-动态染色数.证明了:(1)若G是g(G)≥ 5的平面图且r ≥ 15,则ch(?)(G)≤r+5;(2)若G是g(G)≥ 7的平面图且r ≥ 16,则(?)(G)≤ r+1.第五章研究了稀疏图的列表r-动态染色,给出了稀疏图的列表r-动态染色数至多为r+1的一些充分条件.证明了对满足下列情形之一的图G,有ch(?)(G)≤ r+1:(1)mad(G)<18/7且 r≥ 8;(2)mad(G)<5/2 且 r≥ 6;(3)mad(G)<12/5且 r ≥5;(4)mad(G)<2.8-ε 且 r ≥f(ε)=16/5ε-2,其中 0<ε≤1/10.(本文来源于《浙江师范大学》期刊2019-03-01）

于筱蔚^[3]（2018）在《图的点可区别染色和标号》一文中研究指出本文中不加特殊说明,所有图都是有限简单图.我们分别用V(G),E(G),△(G)和δ(G)来表示图的点集,边集,最大度和最小度.本文主要研究与四色猜想和图的非正则强度有关的图染色问题,主要包括:局部非正则边染色,列表1-2-3猜想,邻和可区别边染色,反魔幻标号猜想,图的DP-染色.一个图被称为是局部非正则的,如果图中任意两个相邻顶点的度都不相同.图的局部非正则k-边染色是指用集合{1,2,...,k}中的元素给边染色使得图中同种颜色导出的子图都是局部非正则的.但并不是所有的图都存在局部非正则边染色.如果G存在一个局部非正则边染色,那么我们称图G是可分解的.在2015年,Baudon,Bensmail,Przybylo和Wozniak猜想每个可分解的图都存在局部非正则3-边染色.近来,Bensmail等人证明了第一个一般图的局部非正则边色数的上界,为328.后来Borut等人又将这个界改进到了 220.本文中,我们将通过证明任意的可分解的二部图都存在局部非正则5-边染色来推广一般图的结论,得到一般可分解图的上界是184.如果一个图中不含孤立边,那么我们称这个图为常规图.图G的kk-边赋权φ是指函数φ:E(G)→ {1,2,...,k}.我们称kk-边赋权是正常的如果有∑e(?)uφ(e)≠∑e(?)vφ(e)对任意的边uv∈E(G)都成立.2004年,Karonski,Luczak和Thomason提出了着名的1-2-3猜想:任意的常规图G都存在一个正常的3-边赋权.这个猜想得到了广大学者的关注,目前最好的结果是= 5.我们称图G是(k,k')-可选的,如果对任意的列表分配L,其中每个顶点v ∈(G)的列表L(v)含有有k个实数,每条边e∈ E(E(的列表L(e)含有kk'个实数,G都存在一个全赋权φ:V(G)∪E(G)→R五使得φ(z)∈L(z)对每个z ∈ V(G)∪E(G)都成立,并且任意两个相邻的顶点都含有不同的点和,这里顶点u∈V G 的点和是指v的权值与点v关联的边上的权值的和.在2011年,Wong和Zhu猜想每个常规图是(1,3)-可选的.显然,这个猜想是1-2-3猜想的列表形式.一些特殊图比如完全图,完全二部图,树,一些特殊图的笛卡尔积,以及最大平均度小于11/4的常规图都是(1,3)-可选的.在2015年,Wang和Yan证明了任意的常规图G是(1,4△(G)+8/3])-可选的.我们运用组合方法证明了任意常规图G是(1,△(G)+ 2)-可选的.一个图的正常边染色是指用集合{1,2,...,k}中的元素给图中的每条边染色使得任意相邻两条边染不同的颜色.如果我们在1-2-3猜想的基础上加上“正常边染色”的限制,那么这种染色就变成了邻和可区别k-边染色,或者简写为NSD-k-边染色.在2013年,Flandrin等人研究了树,圈,完全图,完全二部图的邻和可区别边染色.基于这些结果,他们猜想如果G是一个至少含有3个顶点且G≠ C5 的连通图,那么χ'∑≤△(G)≤△(G)+ 2.Flandrin等人还证明了对于最大度△(G)>2的连通图G有χ'∑(G)≤[7△(G)-4/2]成立.Wang和Yan将这个界改进到了[10△(G)+2/3].后来,Przybylo证明了 ch'∑(G)<2△(G)+ col(G)-1,其中col(G)是图G的染色数.最近,Przybylo和Wong证明了ch'∑(G)≤ △(G)+ 3col(G)-4.我们给出了一般图的上界 ch'∑(G)≤ △(G)+「5col(G)+1/2],这个界覆盖了之前的结果.Dong等人研究了稀疏图的NSD-k-边染色.更具体地.他们证明了下面的结果:设G是一个常规图.如果△(G)≥ 5且mad(G)<5/2,那么X'∑(G)≤ △(G)+ 1.其中mad(G)=max{ 2|E(H)|/|V(H)||H(?)G}.后来.Gao等人将这个界从5/2改进到8/3.我们将8/3提高到3-2/△(G).同时,我们还证明了如果G是最大度△(G)≥ 5且mad(G)<3的常规图,那么χ'∑(G)≤ △(G)+ 2.另外,我们证明了如果△(G)= 3且mad(G)<5/2,那么 χ'∑(G)≤ 5.含有m条边的图G的一个kk-标号是指从E(G)到含有m + k个正实数的集合S的单射.顶点v∈()的点和是指与v关联的所有边上的颜色的加和.如果在图G的一个k-标号中,任意两个顶点的点和都不相同,那么我们称这样的k-标号为点可区别标号.一个k-标号是反魔幻标号如果它是一个点可区别标号并且标号集合是S ={1,2,...,m}.如果一个图存在反魔幻标号,那么我们称这个图是反魔幻的.如果在一个k-标号中任意两个相邻的顶点的点和不同,那么这个k-标号是局部k-反魔幻标号.我们称一个图是局部反魔幻的,如果它存在一个局部反魔幻标号.在1990年,Hartsfield和Ringel猜想每个常规的连通图都是反魔幻的.本文我们将研究与这一猜想相关的两个问题.对任意一个简单图G,给图中所有的边一个方向使得图G变成一个有向图G,我们称G为图G的定向.如果图G存在一个定向G,并且G存在一个标号使得G中任意顶点的出边上的标号和减去入边上的标号和不同,其中标号集合S ={1,2,...,m},那么我们称G是图G的反魔幻定向.2010年,Hefetz,Mutze和Schwartz引入了这一概念,并且在同一篇文章中提到了下列问题:每个连通图都存在一个反魔幻定向.同时他们证明了几乎所有正则图都存在反魔幻定向.注意到如果一个二部图是反魔幻的,我们给每条边一个从一部分顶点到另一部分顶点的方向,那么这就是一个反魔幻定向.因此正则二部图存在一个反魔幻定向.一个二部图是双正则的如果每部分顶点都有相同的度.我们证明了任意的双正则二部图存在一个反魔幻定向.作者Arumugam等人以及Bensmail等人在不同的文献中分别猜想每个常规连通图G用集合S = {1,2,…,|E(G)|}中的元素标号的话都存在一个局部反魔幻标号.Bens-mail等人证明了当标号集合是S = {1,2,...,|E(G)| + 6}时,最大度是3的图存在一个局部6-反魔幻标号.我们直接证明了最大度是3的图是局部反魔幻的.在他们的同一篇文章中,还证明了当标号集合是S={1,2,...,|EG)| +4}时,每个常规的2-退化图存在一个局部4-反魔幻标号;如果标号集合是S = {1,2,…,|E(G)| + k+}的话,每个常规图存在一个局部kk-反魔幻标号,其中k = min{2△(G),|E(G)|}.我们证明了两个关于一般图的结论.设G是一个常规图,最大度是△(G).如果G中的所有顶点的度都是奇数,那么G是局部(△(G)+ 1)-反魔幻的;否则的话,G是局部△(G)-反魔幻的.我们还证明了 G是局部「3col(G)+3/2]-反魔幻的.在解决平面图的列表点染色问题时,Dvorak和Postle介绍了一个新的概念:DP-染色(他们称之为对应的染色).图G的DP-染色把从列表L中找一个正常点染色问题归结为在一个辅助图H(G,L)中寻找一个比较“大”的独立集的问题,其中辅助图H(G,L)的点集是{(v,c):v∈ V(G)且c ∈ L(v)},边集包含两部分:·对于任意的顶点v ∈ V(G),(v,c)与(v,c')相邻,其中c,c'∈'L(v);·对于任意的边uv ∈E(G),(u,L(u)与(v,L(v))之间的边是一个任意的匹配(可能为空).这个思想来源于Plesnevic和Vizing把正常k:-染色问题归结为在笛卡尔积G□Kkk中寻找大小为|V(G)|的独立集的问题.如果对于任意的列表L,其中对任意顶点v ∈V(G),有|L(v≥ kk,H中都存在一个大小为|V(G)丨的独立集,那么我们称图G是DP-kk-可染的.称最小的k为图G的DP-染色数,记作χDP(G).显然χDP(G)≥χl(G)对任意的图都成立,但是它们之间相差甚远.我们在第四章中介绍了简单图的DP-染色,并且证明不含4-圈和3-圈相邻的可平面图的DP染色数是4.(本文来源于《山东大学》期刊2018-05-23）

胡杰^[4]（2018）在《图的邻点可区别全染色与局部反魔幻标号》一文中研究指出图的染色与标号问题是图论中的重要分支,其研究历史久远.作为图论发展的先导之一:四色定理,就是典型的染色问题.一直以来,图的染色与标号问题备受关注,它们不仅在图论上扮演重要角色,而且在社会科学、生命科学等方面都有着广泛应用.图的染色与标号本质上都是从图的点集或边集到实数集的映射.我们首先研究的是平面图的邻点可区别全染色问题.图G的k-全染色是指用集合[k]中的颜色(即元素)对图的点和边同时进行染色,使得相邻的点、相邻的边以及相关联的点和边都染不同颜色.对于G的一个k-全染色φ,我们用C(v)来表示由点v以及v的所有关联边的颜色构成的集合.我们称点v和点u是冲突的,如果两点相邻且Cφ(v)=Cφ(u).如果G中任意两个邻点都不冲突,则称k-全染色φ是邻点可区别的.我们将能够使得G具有邻点可区别全染色的最小的颜色数k称为图G的邻点可区别全色数,记作χ"a(G).2005年,Zhang等人首次提出这种染色并猜想:对于至少有两个点的连通图G,均有χ"a(G)≤△(G)+ 3.Cheng等人已经证明对于最大度至少为10的平面图,上述猜想成立.本文在第二章中证明了对于最大度△(G)≥9的平面图G,有χ"a(G)≤ △(G)+ 3,改进了已有的结果,从而推动猜想的解决.进一步,对于最大度△(G)≥ 10的平面图G,我们得到了更好的上界,即χ"a(G)≤ △(G)+ 2.在第叁章中,我们主要考虑图的局部k-反魔幻定向.设D是图G的一个定向且G的边数为m,D的局部k-反魔幻标号是指这样一个映射:将D的边集映射到[m + k],使得任意两条边的标号(即像)不同,且任意两个邻点的点和互异,其中点和是指该点所有入边的标号之和减去所有出边的标号之和.如果D有局部k-反魔幻标号,那么就称D是图G的一个局部k-反魔幻定向.当k = 0时,简称局部k-反魔幻标号(定向)为局部反魔幻标号(定向).之所以考虑该问题,是受着名的反魔幻标号猜想和1-2-3猜想的启发.反魔幻标号猜想自1990年被提出以来受到广泛关注,但至今仍未完全解决,其难度在于不仅要求任意两条边的标号互异,而且任意两个点所关联的边的标号之和也要不同.而1-2-3猜想只要求区分邻点,受此启发,我们开始研究图的局部反魔幻标号,进而推广到有向图.Chang等人猜想:每一个连通图都存在一个局部反魔幻定向.本文中,我们证明了每一个d-退化图都存在一个局部(d + 2)-反魔幻定向,并且该结论对于列表形式也成立,其中列表中元素均为正实数.由于平面图是5-退化的,因此每一个平面图都存在一个局部7-反魔幻定向.(本文来源于《山东大学》期刊2018-03-01）

张冰^[5]（2016）在《几类图的r-hued染色和距离标号》一文中研究指出图论是离散数学的一个重要分支,图的染色问题是图论中重要的研究领域之一,其在科学技术和工程领域中有广泛的应用.在图的染色问题中,图的r-hued染色和距离标号都是近几十年来研究的热点,具有重要的理论研究价值与应用前景.本论文主要研究两类直积图的r-hued染色和点积图与无限正则叁角网格图的距离标号问题.分别得到了两类直积图的r-hued色数,点积图L(2,1)-标号数的上界和无限正则叁角网格图的L(3,2,1)-标号数的新下界.论文共分五章,各章的主要工作叙述如下：第1章简单地介绍了图论的发展,本文的研究背景、内容以及预备知识.第2章主要研究路与路的直积图的r-hued染色和路与圈的直积图的r-hued染色.关于图的2-hued染色,已经获得了很好的研究结果.但有关r≥3的研究结果还很少,本章利用构造、反证和图的同构等方法得到了两类直积图的r-hued色数.第3章主要研究点积图的L(2,1)-标号问题Griggs和YeA关于图的L(2,1)-标号数的猜想是距离标号问题中着名的猜想,至今仍没有完全解决.本章通过图的一种标号算法和结构分析等方法得到了点积图的L(2,1)-标号数的上界,从而也证明了对于点积图,Griggs和Yeh提出的关于图的L(2,1)-标号数的猜想是正确的.第4章主要研究无限正则叁角网格图的L(3,2,1)-标号问题.本章利用反证、结构分析等方法得到了无限正则叁角网格图的L(3,2,1)-标号数的一个新下界,改进了已有的结果.最后,第5章对本论文进行了简单的总结和展望.(本文来源于《中国矿业大学》期刊2016-06-01）

曹萌萌^[6]（2012）在《图的几种N（p，q）标号问题与图的两类染色问题》一文中研究指出图的标号问题是图论中的一类重要问题,它研究图的各类剖分问题,其各种问题都有广泛的应用背景.其中一个问题的理论研究背景是频道分配问题.灵敏度较高的基本频道分配问题要求相互干扰的站台获得的频道不同,干扰同一站台的频道之间不能相差太小,转化为图论问题就是要求相邻的点获得的标号不同,同一点的邻点标号要有间隔.基于此,Griggs和Yeh在1992年提出了着名的L(2,1)-标号问题；孙磊老师于2008年提出了邻域限制标号问题.定义1对于正整数k,图G的一个k-L1,2-标号是满足以下条件的一个映射c:V(G)→{0,1,2,…,k},(1)若uv∈E(G)则c(u)≠(v);(2)(?)u,v∈V(G)若(?)w∈V(G)使得u,v∈NG(w)则|c(u)-c(v)|≥2.使得图G有一个k-L1,2-标号的最小的正整数k称为图G的邻域限制标号数,记为L1,2(G).基于以上的研究,本文给出了两种可应用于图的频道分配问题的非完全邻域限制标号SN(p, q)和完全邻域限制标号TN(p,q). SN(p,q)标号要求相邻的点得到的标号不同,并且度不小于一定值p的点的邻点得到的标号至少差q,也就是说,相邻的站台得到的频道不同,并且干扰同一站台的频道数达到一定值p时,各频道之间至少差q. TN(p,q)标号不仅要求相邻的点得到的标号不同,度不小于一定值p的点的邻点得到的标号至少差q,而且要求度小于p的点的邻点得到的标号至少差1.即在SN(p, q)标号要求的基础上,还要求干扰同一站台的频道数未达到一定值p时,各频道之间至少差1.其定义如下：定义2对于正整数k,p,q,其中q≥2,图G的一个k-N(p, q)标号是一个映射c:V(G)→{0,1,2,…,k},(1)对任意的u,v∈V(G)若u,v间的距离d(u,v)=1,则c(u)-c(v)|≥1;(2)若w∈V(G)且w的度d(w)≥p则(?)u,v∈NG(w),|c(u)-c(v)|≥q.图G的满足(1)(2)的标号称为G的非完全邻域限制标号SN(p, q)使得图G有一个k-SN(p, q)标号的最小的正整数k称为图G的非完全邻域限制标号数,记为sLp,q(G).(3)d(w)<p时,任意的u, v∈NG(w),|c(u)-c(v)|≥1图G的满足(1)(2)(3)的标号称为G的完全邻域限制标号TN(p, q)使得图G有一个k-TN(p, q)标号的最小的正整数k称为图G的完全邻域限制标号数,记为TLp,q(G).易见,当p=△,q=2时,TLp,q(G)=L1,2(G).图的染色问题也是图论领域中一个重要的部分,因此数学家们相继提出了各类染色问题,并且已深入的研究了许多经典的染色问题,如图的面染色,点染色,边染色和全染色.随着图的染色问题的不断发展,数学家们在传统的染色的基础上添加各种限制,提出了许多新的图的染色问题的分支.其中由赖洪建等人于2006年提出的条件染色就是一个新的分支.定义3对于正整数k和r,图G的一个正常(k,r)-染色是满足以下条件的一个映射c:V(G)→{1,2,…,k},(1)若uv∈E(G)则c(u)≠c(v);(2)对(?)v∈V(G),|c(NG(v))|≥min{|NG(v)|,r}.对于固定的r,使得G有一个正常(k,r)-染色的最小正整数k称为图G的条件色数,记为Χr(G).图的单射染色问题也是一类重要的染色问题.一个图的单射染色就是要求图中任意一点的邻点获得的颜色彼此不同.本文第一章主要介绍了文章中所涉及的一些概念,符号和术语以及图的染色问题和图的几类标号问题.在第二章中,我们研究了图的SN(p,q)标号问题和TN(p,q)标号问题,给出了一些图的SN(p,q)标号数和TN(p,q)标号数.第叁章第一节综述了条件染色的发展,并给出了一个新结果.第二节主要研究了几类特殊图的正常单射染色.本文主要得到了以下结果：定理2.2.2若图为完全图Kn,则TLp,q(Kn)=SLp,q(Kn)=(n-1)q.定理2.2.3若图为完全二部图Km,n, m≤n,n≥p则(1)若m=n,则SLp,q(Km,n)=TLp,q(Km,n)=(n-1)q+1.(2)若m<n,则SLp,q(Km,n)=TLp,q(Km,n)=(n-1)q.定理2.2.5若图G仅有一个度不小于p的顶点v,且|V(G)|=n,dG(v)=Δ则(1)(a)若(Δ-1)q≥n-1,则TLp,q(G)=(Δ-1)q;(b)若(Δ-1)q<n-1,则TLp,q(G)≤n-1.(2)(a)若(Δ-1)q≥2Δ,则SLp,q(G)=(Δ-1)q;(b)若(Δ-1)q<2Δ,则SLp,q(G)≤2Δ.定理2.2.6图G仅有两个相邻的度不小于p的顶点u,v,且d(u)=d(v)=s,|V(G)|=n. u,v无公共邻点,且NG[v]与NG[v]中的点除u,v外不相邻,则(1)若q(s-1)≥n-2,则TLp,q(G)=SLp,q(G)=(s-1)q+1;(2)若q(s-1)<n-2,则TLp,q(G)≤n-1;(a)若(s-1)(q-2)≥s,则SLp,q(G)=(s-1)q+1;(b)若(s-1)(q-2)<s,则SLp,q(G)3s-1.定理2.2.7若图G仅有两个相邻的度不小于p的顶点u,v,且d(u)=d(v)=s,|v(G)|=n.u,v有m个公共邻点,且除这m个点外,NG(u)与NG(v)中的点互不相邻,则(1)若(s-1)(q-1)≥n+m-2s则TLp,q(G)=SLp,q(G)=(s-1)q+1;(2)若(s-1)(q-1)<n+m-2s则TLp,q(G)≤n-s+m;(a)若(s-1)(q-1)≥s,则SLp,q(G)=(s-1)q+1;(b)若(s-1)(q-1)<s,则SLp,q(G)≤2s.定理2.2.8若图G仅有两个相邻的度不小于p的顶点u,v,其中|V(G)|=n,d(u)=s,d(v)=t,s>t,若u,v有m个公共邻点,且除这m个点外,NG(u)与NG(u)中的点互不相邻,则(1)若(s-1)q≥n+m-t,则TLp,q(G)=SLp,q(G)=(s-1)q;(2)若(s-1)q<n+m-t,则TLp,q(G)≤n-t+m;(a)若(s-1)q≥t+s,则SLp,q(G)=(s-1)q;(b)若(s-1)g<t+s则SLp,q(G)≤t+s.定理2.2.9若图G仅有两个相邻的度不小于p的顶点u,v,其中|V(G)|=n,d(u)=s,d(v)=t,s>t若u,v无公共邻点,且NG[u]与NG[v]中点除u,v外互不相邻,(1)若(s-1)g≥n-1则TLp,q(G)=SLp,q(G)=(s-1)q;(2)若(s-1)q<n-1,则TLp,q(G)≤n-1;(a)若(s-1)(q-1)≥2t,则SLp,q(G)=(s-1)q;(b)若(s-1)(q-1)<2t,则SLp,q(G)≤2t+s-1.定理2.2.10若图G仅有两个度不小于p的顶点u,v,且u,v有m个公共邻点,且NG[u]∪Ng[v]中除m个公共邻点外其余点两两不相邻,|V(G)|=n,d(u)=s,d(v)=t,s>t则(1)若(s-1)g≥n-t+m-1,则TLp,q(G)=SLp,q(G)=(s-1)q;(2)若(s-1)q<n-t+m-1,则TLp,q(G)≤n-t+m-1;(a)若(s-1)(q-1)≥t+2,则SLp,q(G)=(s-1)q;(b)若(s-1)(q-1)<t+2,则SLp,q(G)≤t+s+1.定理2.2.11若图G仅有两个度不小于p的顶点u,v,其中|V(G)=n,d(u)=s,d(v)=t,s≥t,u,v无公共邻点,且d(u,v)>3,则(1)若(s-1)g+t≥n-1则TLp,q(G)=SLp,q(G)=(s-1)q;(2)若(s-1)g+t<n-1则TLp,q(G)≤n-t-1；(a)若(s-1)g≥s+t+1,则SLp,q(G)=(s-1)q;(b)若(s-1)g<s+t+1则SLp,q(G)≤t+s+1.定理3.1.9若图G为仅有一个最大度点v的连通图,V(G){v}的度至多为t,其中0<t≤[△/2]-1,△(G)≥3.则xr(G)≤(△-t)2.定理3.2.5若图G为仅有一个最大度点v的连通图,d(v)=Δ,T=G-{v}为一棵树,其中NG(v)中有p个1度的点,m=(?)|NG(v)∩NT[u]|,则χi(G)≤2Δ-p-m+1.推论3.2.6图G中存在一点v,d(v)=t≤Δ,T=G-{v}为一棵树,其中NG(v)中有p个1度的点,m=(?)|NG(v)∩NT[u]|则χi{G)≤Δ+t-p-m+2.定理3.2.7图G为连通的,G中存在两个不相邻的点u0,v0满足G-{u0,v0}=T为一棵树,NG(u0)∪NG(v0)|=n-2,A(G)=Δ,s=(?)|NT[u]∩NG(u0)|,t=(?)|NT[v]∩(NG(v0)|,|V(G)|=n,则定理3.2.8图G为连通的,G中存在两不相邻的点u0,v0满足G-{u0,v0}=T为一棵树,m=|NG(u0)∪NG(v0)|<n-2,Δ(G)=Δ,s=(?)|NT[u]∩NG(u0)|,t=(?)|NT[v]∩(NG(v0)|,|V(G)|=n则推论3.2.9图G为连通的,G中存在相邻的两点u0,v0满足G-{u0,v0}=T为一棵树,m=|NG(u0)∪NG(v0)|,Δ(G)=Δ,s=(?)|NT[u]∩NG(u0)|,t=(?)|NT[v]∩(NG(v0)|,|V(G)|=n,则χi(G)≤Δ+m-s-t+3.定理3.2.11图G为连通的,G中存在两个不相邻的点u0,v0满足G-{u0,v0}=Km,n=(X,Y)其中m≥n≥2,且rmax{d(u0), d(v0)}<n,NG(u0)(?)X则定理3.2.12图G为连通的,G中存在两个相邻的点u0,v0,满足G-{u0,v0}=Km,n=(X,Y)其中m≥n≥2,且max{d(u0), d(v0)}<n, NG(u0)(?)X,则定理3.2.13图G为连通的,Km,n是G的生成子图,G0=GE(Km,n)其中m≥n≥2则χi(G)≤m+n.定理3.2.15图G为连通的,T是G的一棵支撑树,G0=GE(T),Δ(T)=Δ(G).(1)若G0为m条匹配边,其中m1条边关联树T中距离为2的点,则χi(G)≤Δ+1+m-m1.(2)若G0为一条长为l的路,则(3)若G0为一棵树,则χi(G)≤2Δ-1.(4)若G0为一个圈,其中|V(G0)|=n≥3,则(本文来源于《山东师范大学》期刊2012-04-10）

于永^[7]（2012）在《图的[r，s，t；f]-染色及（p，1）-全标号问题》一文中研究指出图论最早起源于18世纪叁十年代。大数学家Eulcr在1736年完成的关于哥尼斯堡七桥问题的论文,被公认为是研究图论的开山之作。由此,Euler也被认为是图论研究的鼻祖。伴随着图论的兴起和发展,这门新兴的学科逐渐在化学、生物学、信息论、控制论、网络理论、博弈论及计算机科学领域产生了广泛的应用。染色理论作为图论最经典的问题之一更是受到了广泛关注。由着名的“四色猜想”开始,染色理论逐步成熟和壮大,先后产生了点染色、边染色、全染色、列表染色、频道染色、条件染色等一系列新的研究方向。在现实生活中染色理论有着广泛的应用背景,如时间表安排问题、工序问题、教室分配问题、选址问题、生产调度问题、频道分配问题等等。本文所考虑的图都是连通的简单有限图。通常情况下,V(G),E(G)分别表示一个图G的顶点集合和边集合。|V(G)|,|E(G)|分别表示图G的顶点数和边数,有时也称为图的阶和大小。图G的一个正常k-全染色是指用k种颜色对V∪E中的元素进行着色,使得任何两个相邻接或相关联的元素获得不同的颜色。使得图G存在一个正常κ-全染色的最小正整数κ称为图G的全色数,记作χ"(G)。若只对图G的顶点(边)进行着色,则称为是图的一个点(边)染色。显然,全染色是对点染色和边染色的推广。Bchzad和Vizing分别在其论文中独立地给出了如下着名的全染色猜想。全染色猜想.对任意图G,都有χ"(G)≤△+2。尽管围绕着这个猜想已有大量的文献,该问题却至今仍未得到完全解决。本文主要讨论两类新的染色问题,也可以称为两类标号问题,即图的[r,s,t；f]-染色及(p,1)-全标号。二者都可以看做是图的全染色的进一步推广令r,s,t是叁个非负整数,,是一个定义在图G的顶点集合V上取值为正整数的函数。图G的一个[r,s,t;f]-染色即给图的每个顶点和每条边都从颜色集C={1,2,…,k}中分配一种颜色使得相邻的顶点获得的颜色差不小于r；每个顶点所关联的边满足(1)获得不同颜色的边的颜色差不小于s并且(2)获得相同颜色的边数不超过f(v)；相关联的点和边所获得的颜色差不小于t。我们把使得图存在[r,s,t;f]-染色的最小的颜色数k称为图G的[r,s,t;f]-色数,并记作Xr,s,t,f(G)。图的[r, s,t;f]-染色是我们首次提出的一个新的染色概念,它可以看作是对[r,s,t]-染色的进一步推广。[r,s,t]-染色的概念最初是由Kcmnitz和Marangio提出的。他们研究了该染色的一些性质并用足球比赛的日程安排问题举例说明了其实际的应用价值。Kemnitz和Marangio给出了参数Xr,s,t(G)的一些上下界并针对参数r,s,t分别取一些特定值的情况得到了一系列的结果。[r,s,t]-染色是一个难度比较大的问题,即使对于星K1,。和完全图Kn等一些简单的图类也没有完全地解决。频道分配问题实质上是一个如何分配无线电频道资源以实现最合理应用的最优化问题。这个课题曾经被AT&T贝尔实验室,美国国家安全局等多个机构的研究部门所研究。在频道分配问题中,我们需要将无线电频率(图论模型中用一些正整数代替)分配给不同的无线电接收装置。为了避免互相干扰而影响信号的传送,如果两个无线电接收装置紧挨着,则要求分配给它们的频率段至少差2,如果两个无线电接收装置靠的比较近但不是紧挨着(比如相隔一个无线电接收装置),则要求分配给它们的频率段至少差1。受这个问题的启发,RogerYch提出了L(2,1)-标号问题并很快被推广到L(p,q)-标号的形式。图的关联图是指将图G中的每条边都用一条长为2的路代替所形成的新图。Havet将一个图的关联图的L(p,1)-标号问题定义为图的(p,1)-全标号问题。该问题也可以被看作是全染色问题的一种推广形式。一个图G称为是可k-(p,1)-全标号的当且仅当存在一个将V(G)∪E(G)映射到颜色集合{0,1,…,k}的函数c满足：(1)若uv∈E(G),则|c(u)—c(v)|≥1；(2)若e和e'是G的相邻边,则|c(e)—c(e,)|≥1；(3)若顶点u和边e相关联,则|c(u)—c(e)|≥p.使得G可k-(p,1)-全标号的最小的正整数k称为是图G的(p,1)-全标号数,并记作λpT(G)。本文主要讨论图的[r,s,t;f]-染色及(p,1)-全标号。文章的主要内容及结构安排如下。第一章是绪论部分。本章的第一小节是对文中出现和用到的一些基本概念和符号的简单说明,第二小节则分别从全染色,图的[r, s,t]-染色与,-染色和频道分配问题叁个方面对论文研究内容的背景做了相对完整的介绍,接下来的第叁小节则给出我们所研究的图的[r,s,t;f]-染色及(p,1)-全标号问题的基本定义。最后,本章的第四小节将列出论文中证明的主要结论。第二章主要讨论[r,s,t；,]-染色。在这一章的第一小节中我们先对[r,s,t]-染色的一些背景和已知结果做一个简单的概括,并介绍一些在主要定理的证明中用到的符号和术语。接下来的第二小节是本章的重点部分,在这一节里我们将给出主要的结果及其证明,最后的第叁小节接着给出几个可以继续研究的问题。第叁章主要讨论图的(p,1)-全标号。第一小节对(p,1)-全标号问题的起源和背景做一个简单的介绍并给出(p,1)-全标号猜想,第二小节主要介绍该问题的研究进展和对于一些特殊图类已经取得的结果,第叁小节首先给出一些在主要定理的证明过程中用到的概念和结构性引理,接下来则主要考虑与平面图相关的一些图类的(p,1)-全标号问题,从而为(p,1)-全标号猜想的成立提供新的依据。第四小节将给出关于(p,1)-全标号猜想可以进一步研究的问题。第四章主要讨论图的列表(p,1)-全标号问题。在这一章的第一小节我们先对列表(p,1)-全标号问题做一个总体的介绍,第二小节类比列表全染色猜想给出一个关于列表(p,1)-全标号数上界的猜想,这里不妨称为弱列表(p,1)-全标号猜想,第叁小节主要考虑一些特殊图类,如星、外可平面图、可嵌入欧拉示性数为ε的曲面的图等,通过证明这些特殊图类的列表(p,1)-全标号数的上界,进而为我们所提出的弱列表(p,1)-全标号猜想提供依据。最后一小节给出几个值得做进一步研究的问题。(本文来源于《山东大学》期刊2012-03-20）

孙美姣^[8]（2010）在《图的（p，1）-全标号及图的弱邻点可区分的染色问题》一文中研究指出图理论是一门非常年轻的学科,在许多的科学领域都有着广泛的应用背景.图的染色问题是图理论的一个重要组成部分,而且许多经典的染色问题诸如点染色和边染色等都已经有了深入的研究.随着科技的进步,在各种新的科技问题的背景之下,许多新的染色问题也被相继提出.在无线电网络中分配传播的波段的问题时,产生了一个频道分配问题.如果几个站点是相邻的,为了避免发射的信号相互干扰,那么在给这些相邻的站点分配频道时,它们得到的频道相差至少为2；而且如果两个站点离得近(但不是非常近),那么分配给它们的频道也需要不同.如果把这个问题转化成图论的染色问题就是Griggs和Yeh提出的L(2,1)-标号问题[4].2000年,G.J.Chang等人把它推广到图的L(p,1)-标号[5].图G的L(p,1)-标号是对G的顶点集的一个整数映射L,使得对任意的顶点u,υ满足：(1)若dG(u,v)=1,则|L(u)-L(v)|≥p；(2)若dG(u,v)=2,则|L(u)-L(v)|≥1,(其中dG(u,v)表示u,v两点之间的距离).一个图G的关联图[6]是指把图G的每一条边用长为2的路代替.图G的关联图的L(p,1)-标号,是对G的一个特别的全染色,这种全染色就是由Havet和Yu提出的(p,1)-全标号[7].设p是一个正整数,图G的一个k-(p,1)-全标号是一个映射f：V(G)∪E(G)→{0,1,…,κ｝,使得：(1)G的任意两个相邻的顶点u,v,有|f(u)-f(v)|≥1；(2)G的任意两条相邻的边e,e',有|f(e)-f(e')|≥1；(3)G的任意两个关联的点u和边e,有|f(u)-f(e)|≥p.我们称这样的一个标号叫G的(p,1)-全标号.(p,1)-全标号的跨度是指标号中的最大标号与最小标号的差.G的(p,1)-全标号的最小跨度叫(p,1)-全标号数,记作λPT(G),即λPT(G)=min｛k|G有一个k-(p,1)-全标号｝.图的邻点可区分的边染色(邻强边染色)[8]和邻点可区分的全染色[9]是由张忠辅老师首先提出的,在数据传输问题上有一定的应用背景,但是由于限制的条件比较强目前仅在树,圈,完全图等图类上得到了解决.Hajo Broersma[10]曾经把古典的顶点标号进行变形,把对原图G的限制放松到主干道上,提出了一种新的染色一主干道染色(Back Bone coloring).我们沿用此思想在本文中将邻点可区分的全(边)染色的条件限制在支撑树上,提出了如下两种定义：定义1给定一个简单连通图G,k为一个正整数,f是G的一个正常边染色,f：E(G)→{1,2,…k｝,设、T是G的一棵支撑树,记C(u)={f(uw)|w∈N(u)},如果对任意的uv∈E(T)满足C(u)≠C(v),则f称为G的T-邻强边染色.记XTas(G,T)=min{k|G有一个k-T-邻强边染色｝,定义2给定一个简单连通图G,k为一个正整数,f是G的一个正常全染色,f：V(G)∪E(G)→{1,2,…k｝,设T是G的一棵支撑树,记C(u)={f(u)∪f(uw)|w∈N(u)｝,如果对任意的uv∈E(T),满足C(u)≠C(v),则f称为G的T-邻点可区分的全染色.记XTat(G,T)=min{k|G有一个k-T-邻点可区分的全染色}.显然这两个定义的条件要比张忠辅老师提出的邻点可区分的全(边)染色的定义要弱一些,所以我们称这两种新的染色问题为图的弱邻点可区分的染色问题.在本文的第一章里,我们主要介绍了文章中所涉及的一些概念、术语和符号以及图染色问题的发展情况.在第二章中,我们研究了图的(p,1)-全标号,给出了当p=3,Δ≥9时,全标号的一个上界和特殊图的(p,1)-全标号.第叁章中研究了T-邻点可区分的全(边)染色,并给出了这两种染色在任意图上的一个上界,以及在一些具体图类上的上界.定理2.1.5设任意图G,Δ(G)≥9,则λ3T(G)≤2Δ(G)+1.定理2.2.4非正则二部图G,Δ(G)=Δ,且图G的最大度点导出子图包含K1,Δ-1,则λpT(G)=Δ+p,(p≥22).定理3.1.2若图G是连通图,Δ(G)=Δ,则对G的任意支撑树T,χ'Tas(G,T)≤2Δ+1.定理3.1.4若图G是简单连通图,Δ(G)=Δ,T是G的任意一棵支撑树,则χTat(G,T)≤3Δ+2.定义3.2.1若简单图G=(V(G),E(G)),V(G)={v1,v2,…,vn｝,图G'的点集和边集定义如下：V(G')={v1,v2,…,vn,v1',v2',…,vn'｝,E(G')＝{vivj,vi'vj,vivj',vi'vj'|vivj∈E(G)｝,则图G'称为图G的点分裂图.根据点分裂图的定义可知,原图和点分裂图满足：Δ(G')=2Δ(G),δ(G')=2δ(G)且对任意的v∈V(G'),dG'(v)=2dG(v).定理3.2.1图G'为连通图G的分裂图,则G'存在一棵支撑树T',使得χ'Tas(G',T')≤3/2Δ(G')+1.定理3.2.2若图G/为连通图G的分裂图,则G'存在一棵支撑树T',使得χTat(G',T')≤5/2Δ(G')+2.定义3.3.1设G1,G2为简单图,若|G1|=n1,V(G1)={u1,u2,…,un1}|G2|=n2,V(G2)={υ1,u2,…,un2｝,G1×G2的点集和边集定义如下：V(G1×G2)={uivj|i=1,2,…,n1,J=1,2,…,n2｝；E(G1×G2)={(uivj)(ukvl)|vj=vl且(ｕiｕk)∈E(G1)或ui=uk且(vjvl)∈E(G2),i,k=1,2,…,n1；J,ι=1,2,…,n2｝.则G1×G2为G1,G2的笛卡尔乘积图.定理3.3.1若连通图G1,最大度为Δ(G1),连通图G2,最大度为Δ(G2),Δ(G1)≤Δ(G2),则其笛卡尔乘积图G1×G2,存在支撑树T,使得χ'Tas(G1×G2,T)≤2Δ(G1)+Δ(G2)+1.定理3.3.2若连通图G1,最大度为Δ(G1),连通图G2,最大度为Δ(G2),Δ(G1)≤Δ(G2),则其笛卡尔乘积图G1×G2,存在支撑树T,使得χTat(G1×G2,T)≤3Δ(G1)+2Δ(G2)+2.另外我们还研究了一些特殊图类的T-邻点可区分的全染色和边染色.(本文来源于《山东师范大学》期刊2010-04-10）

马帅^[9]（2009）在《特殊图类的标号染色》一文中研究指出图G是一个叁维有序组合,由非空的顶点集合V(G),边集E(G),以及一个点边的关联函数ψ_G组成.图G的平方图G~2定义为:图G~2与G有相同的点集,图G~2中的两顶点为邻点当且仅当在图G中与此两点对应的点的距离小于等于2.我们涉及的图都是有限的,无环的且没有重边.图的点染色的概念:如果图G的顶点可分为k个集合:V_1,V_2,…,V_k,且每个V_i都是独立的,即任意一个顶点集合中没有邻接点,则称图G为k-可染色的,最小的那个k值称为图G的颜色数目,记作χ(G).图G的L(p,q)-标号染色:对于任意的整数p≥0,q≥0,若存在一个映射L:V(G)→{0,…,k},对于图G中的任意两个顶点u,v满足:·| L(u)-L(v)|≥p,若dist(u,v)=1·| L(u)-L(v)|≥q,若dist(u,v)=2则称其为图G的一个L(p,q)-标号染色.对于其中最小的k值,记为λ_q~p(G).路P_n是一个这样的图:其点集合为V(P_n)={v_1,v_2,…,v_n},其边集合为E(P_n)={v_1v_2,v_2v_3,…,v_(n-1)v_n},其中点v_1,v_n称为路P_n的端点.通常将路P_n记为v_1,v_2,…,v_n.圈C_n是—个这样的图:其点集合为V(C_n)={v_1,v_2,…,v_n},其边集合为E(C_n)={v_1v_2,v_2v_3,…,v_(n-1)v_n,v_nv_1},因为圈的顶点首尾相连,所以其也不存在端点.我们称圈C_n为奇圈,当且仅当n为奇数时;我们称圈C_n为偶圈,当且仅当n为偶数时.完全图K_n是指由n个顶点组成的一个图,其中任意两个点之间都有边相连。笛卡尔积图:对图G和H,设V(G)={u_1,u_2,…,u_m}和V(H)={v_1,v_2,…,v_n}.它们的笛卡儿积图G×H定义为:V(G×H)={w_(ij)=E(H),或j=l和(u_i,u_k)∈E(G).平面图定义:若图G可在平面图上画出,且其所有的边只在顶点处相交,则G为平面图.我们得到以下结论:对于任意的图G的L(p,q)-标号染色及其平方图G~2的点染色有以下结论成立:以及由此结论得出的推论:对于路P_m和P_n(m≥3,n≥3),其迪卡尔积图P_m×P_n,有如下结论成立:对于圈C_m和路P_n(m≥3,n≥3),其笛卡尔积图G_m×P_n,有如下结论成立:对于完全图K_m和路P_n(m≥3,n≥3),其笛卡尔积图K_m×P_n,有如下结论成立:对于完全图K_m和圈C_n(m≥3,n≥3),其笛卡尔积图K_m×C_n,有如下结论成立:对于圈C_m和圈G_n(m≥3,m≠5,n≥3),其笛卡尔积图C_m×C_n有如下结论成立:对于平面图G,有以下结论成立:(本文来源于《山东大学》期刊2009-04-30）

刘晓晓^[10]（2009）在《有邻域限制的图染色问题及图的L（2，1）—标号》一文中研究指出图的染色问题是图论研究中一个活跃的领域,因此各类染色问题被相继提出并加以发展应用,赖宏建等人在2006年提出了条件染色.图的标号问题就是图的染色问题的推广,其理论研究背景是频道分配问题.Griggs和Yeh在1992年提出了L(2,1)－标号问题,作为标号问题的另一种推广,孙磊老师于2008年提出了邻域限制标号问题.条件染色是传统的点染色在理论上的自然地推广,是在文献[2]中首次提出的.对于整数k＞0和r＞0,图G的一个正常(k,r)－染色是一个满足下面两个条件的映射c:V(G)→{1,2…k},(1)若uv∈E(G),则c(u)≠c(v);(2)对任意的v∈V(G),|c(N_G(v))|≥min{|N_G(v)|,r}.对于固定的r,使G有—个正常的(k,r)－染色的最小的k是图G的第r个条件色数,记为_(Xr)(G).由条件色数的定义很显然的得到_(X1)(G)＝_X(G).作为频率设置问题的一个变形, Griggs和Yeh在1992年提出了L(2,1)－标号问题.图G的一个L(2,1)－标号是一个满足下面两个条件的映射c:V(G)→{0,1,2…k},(1)对任意的u,v∈V(G),若d(u,v)＝1,则|c(u)－c(v)|≥2;(2)对任意的u,v∈V(G),若d(u,v)＝2,则|c(u)－c(v)|≥1.当所有的标号都小于等于k时,称图G有一个k－L(2,1)－标号.则使得图G有一个k－L(2,1)－标号的最小的正整数k称为图G的L(2,1)－标号数,记为λ(G).令c是图G的一个的λ(G)－L(2,1)－标号.令c~(-1)(i)＝{v∈V(G)|c(v)＝i}.且令|c~(-1)(i)|表示c~(-1)(i)的基数.若对于一个整数h(0＜h＜k)满足|c~(-1)(h)|＝0,则称h为c的一个洞.图G的洞数,记为ρ(G),是图G的所有λ(G)－L(2,1)－标号中最少的洞的个数.对于一个整数k＞0,图G的一个k－L_(1,2)－标号是一个满足下面两个条件的映射c:V(G)→{0,1,2…k},(1)任意的u,v∈V(G),若d(u,v)＝1,则|c(u)－c(v)|≥1;(2)任意的u,v∈V(G),若存在w∈V(G),使得u,v∈N_G(w),则|c(u)－c(v)|≥2.则使得图G有一个k－L_(1,2)－标号的最小的正整数k称为图G的邻域限制标号数,记为L_(1,2)(G).令c是图G的一个的k－L_(1,2)－标号.令c~(-1)(i)＝{v∈V(G)|c(v)＝i}且令|c~(-1)(i)|表示c~(-1)(i)的基数.若对于一个整数h(0＜h＜k)满足|c~(-1)(h)|＝0,则称h为c的一个洞.本文中Δ(G)表示图G的最大度,δ(G)表示图G的最小度,d(u,v)表示u,v两点在图G中的距离,N_G(v)表示v在图G中的邻域.在本文的第二章我们主要得到了以下结论.引理2.1.1图G是任意简单图,则L_(1,2)(G)≥2(Δ(G)－1).引理2.1.2图G是任意简单图,且L_(1,2)(G)＝2(Δ(G)－1).则任意的最大度点v,c(v)≡1(mod2),且任意的u∈N_G(v),c(u)＝2i(i＝0,1,2…Δ(G)－1).定理2.1.3若图G中有两个最大度点相邻,则L_(1,2)(G)≥2Δ(G)－1.定理2.1.4若正则图G中有奇圈且Δ≥4,则L_(1,2)(G)≥2Δ(G).定理2.1.5图G是圈,则当|V(G)|≡0(mod4)时,L_(1,2)(G)＝3;否则,L_(1,2)(G)＝4.定理2.1.6设图G是k－退化图,Δ≥4且无叁角,则2(Δ－1)≤L_(1,2)(G)≤Δ(6k－3)＋k－3k~2.定理2.2.1设图G是树,Δ(G)≥3,且图G中有两个最大度点相邻,则L_(1,2)(G)＝2Δ(G)－1.定理2.2.3设图G是树,Δ(G)≥3,若图G中无最大度点相邻且任意两个最大度点的距离为偶数,则L_(1,2)(G)＝2(Δ(G)－1).定理2.2.4设图G是树,Δ(G)≥4,若存在一条包含所有最大度点的路.则当图G中无两个最大度点不相邻且存在两个最大度点的距离为奇数时,L_(1,2)(G)＝2(Δ(G)－1).定理2.2.5设图G是树,Δ(G)≥3,若图G中只有一个最大度点,则L_(1,2)(G)＝2(Δ(G)－1).我们证明了当c是G的一个最小的邻域限制标号,且h是c的一个洞,图G具有的下述性质.性质2.3.1图G是任意简单图,若c是G的一个最小的邻域限制标号,且h是c的一个洞,则h－1,h＋1都不是c的洞.性质2.3.2令c是G的一个最小的邻域限制标号,h是c的一个洞.若|c~(-1)(h－1)|≥2或|c~(-1)(h＋1)|≥2且c(u)＝h－1,c(v)＝h＋1,则肯定存在一点x满足d(u,x)≤2且c(x)＝h＋1或一点y满足d(v,y)≤2且c(y)＝h－1.性质2.3.3图G是任意简单图且无叁角,令c是图G的一个最小的邻域限制标号,且h是c的一个洞.若对任意的标号i,满足|c~(-1)(i)|≥2,则若c(v)＝h－1或h＋1,则肯定存在两点v_1,v_2满足d(v,v_1)＝1,d(v,v_2)＝2,c(v_1)＝c(v_2)＝h＋1或h－1且v_2(?)N_G(v_1).性质2.3.4图G是任意简单图且无叁角,令c是G的一个最小的邻域限制标号,且h是c的一个洞.若存在路uv_0v,满足c(u)＝h－1,c(u)＝h＋1且任意的x满足d(u,x)＝2,但c(x)≠h＋1且任意的y可满足d(v,y)＝2,但c(y)≠h－1.则此时|c~(-1)(c(v_0))|＝1.性质2.3.5图G是任意简单图且无叁角,令c是G的一个最小的邻域限制标号, h是c的一个洞,且|c~(-1)(h－1)|＝1,|c~(-1)(h＋1)|≥2.若令c(u)＝h－1,则对任意的v_i满足c(v_i)＝h＋1,存在路uw_iv_i.若任意的v_i满足d(u,v_i)≠1,则|c~(-1)(c(w_i))|＝1.或有且仅有一个v_i满足d(u,v_i)≠1.G是一个简单图,V(G)＝{v_1,v_2,…,v_n},G[I_2]的点集和边集如下定义:V(G[I_2])＝{v_1,v_2,…,v_n,v_1~',v_2~',…,v_n~'},E(G[I_2])＝E(G)∪{v_i~'v_j~',v_i~'v_j|v_iv_j∈E(G)},则G[I_2]称为G的点分裂图.令G＝(V(G),E(G)),V(G)＝{v_1,v_2,v_3,…v_n},M－构造图M(G)的点集和边集是如下定义的, V(M(G))＝{v_1,…v_n,u_1,…u_n,v},E(M(G))＝{u_iv|i＝1,2…n}∪{u_iv_j|v_iv_j∈E(G)}.M－构造图在研究图染色问题的临界性上有重要应用.在本文的第叁章我们讨论了图G与其分裂图G[I_2]的条件色数的关系及图G与其M－构造图M(G)的条件色数的关系,给出了几类特殊图的条件色数.定理3.1.1图G与其分裂图G[I_2]的条件色数的关系如下,定理3.2.1若整数r满足0＜r≤2Δ(G),则任意的图G的M－构造图M(G)满足_(Xr)(M(G))≥r＋2.定理3.2.2图G与M－构造图M(G)的条件色数的关系如下:对任意的正整数k和m,G(k,m)表示一些图的集合.若G∈G(k,m)当且仅当V(G)＝V_0∪V_1∪…V_m,|V_0|＝|V_1|＝…|V_m|＝k且对任意的0≤i≤m,G(V_i)的导出子图是一个空图;对任意的0≤i＜j≤m,G[V_i∪V_j]的导出子图是一个完美匹配.在本文的第四章我们主要研究G(k,m)这类图的L(2,1)－标号问题并得到了以下结论.定理4.1 k≥3,n≥2,若图G∈G(k,n＋1)且包含一个子图H∈G(k,n)使得λ(H)＝2n且ρ(H)＝n,则λ(G)＝2(n＋1).定理4.2 k≥3,若G∈G(k,2),则λ(G)＝4且ρ(G)＝0或2.定理4.3若G∈G(3,3),则λ(G)＝6.定理4.4若G∈G(4,3),则λ(G)＝6.(本文来源于《山东师范大学》期刊2009-04-02）

标号染色论文开题报告

（1）论文研究背景及目的

此处内容要求：

首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。

写法范例：

图的染色问题是图论研究中的重要问题和热点问题之一,标号问题是染色问题的推广,它起源于通讯问题中的信道频率分配问题.1991年,Roberts提出了给相近和非常相近的发射机分配不同的信道,并且非常相近的发射机接收的信道频率要至少相差两个单位.受这一问题的启发,Griggs和Yeh在1992年系统地提出了 L(2,1)-标号问题.这一概念后来被推广到了图的L(p,q)-标号问题.令p,g为正整数,图G的一个k-L(p,q)-标号是指映射f:V(G)→ {0,1,2,…,k},使得对任意的2个顶点u和,若d(u,v)=1,则有 |f(u)-f(v)|≥p,若d(u,v)=2,则有 |f(v)-f(v)|≥q.其最小的 k值称为图 G 的L(p,g)-标号数,记为λp,q(G).图的L(1,1)-标号等价于2-距离染色.2001年,Montgomery在他的博士论文中提出了动态染色.令k,r为正整数,[k]={1,2,..…,k},图G的一个r-动态染色是指一个正常k-顶点染色f,满足对任意的顶点v,都有|f(NG(v))|≥min{d_G(v),r}.其最小的k值称为图G的r-动态色数,记作(?)(G).特别地,当r=△(G)时,r-动态染色就是图的2-距离染色.本学位论文研究与信道频率分配相关的特殊图类的L(2,1)-标号问题和r-动态染色问题.第一章综述了国内外关于L(2,1)-标号问题和r-动态染色问题的研究现状.第二章围绕Griggs-Yeh猜想展开研究.1992年,Griggs和Yeh猜想:对最大度△ ≥ 2的图G,有λ2.1(G)≤△~2.结合权转移方法和零点定理,我们得到了不含某些特殊短圈的平面图的列表L(2,1)-标号数的上界和平面图在最大度和围长限制条件下的列表L(2,1)-标号数的上界.论文的后面叁章围绕赖虹建等人提出的关于平面图r-动态染色的猜想展开研究.2014年,类似Wegner猜想,赖虹建等人提出:对平面图G,若1 ≤ r ≤ 2,则(?)(G)≤r+3;若 3 ≤ r ≤7,则 Xrd(G)≤ r+5;若 r ≥ 8,则 (?)(G)≤[3r/2]+1.第叁章研究了不含特殊短圈的平面图的列表2-距离染色数(即列表△-动态染色数)和平面图的2-距离染色数(即△-动态染色数),得到了:(1)不含4-圈和6-圈的平面图的列表2-距离染色数的上界;(2)平面图G的2-距离染色数的上界,这一结果改进了目前关于最大度△≤7的平面图的2-距离染色数的最好上界.第四章研究了围长至少为5和围长至少为7的平面图的(列表)r-动态染色数.证明了:(1)若G是g(G)≥ 5的平面图且r ≥ 15,则ch(?)(G)≤r+5;(2)若G是g(G)≥ 7的平面图且r ≥ 16,则(?)(G)≤ r+1.第五章研究了稀疏图的列表r-动态染色,给出了稀疏图的列表r-动态染色数至多为r+1的一些充分条件.证明了对满足下列情形之一的图G,有ch(?)(G)≤ r+1:(1)mad(G)<18/7且 r≥ 8;(2)mad(G)<5/2 且 r≥ 6;(3)mad(G)<12/5且 r ≥5;(4)mad(G)<2.8-ε 且 r ≥f(ε)=16/5ε-2,其中 0<ε≤1/10.

（2）本文研究方法

调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。

观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。

实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。

文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。

实证研究法：依据现有的科学理论和实践的需要提出设计。

定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。

定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。

跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。

功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。

模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。

标号染色论文参考文献

[1].李瞳.图的染色标号问题及超图中的彩色匹配[D].山东大学.2019

[2].朱俊蕾.L(2,1)-标号和r-动态染色[D].浙江师范大学.2019

[3].于筱蔚.图的点可区别染色和标号[D].山东大学.2018

[4].胡杰.图的邻点可区别全染色与局部反魔幻标号[D].山东大学.2018

[5].张冰.几类图的r-hued染色和距离标号[D].中国矿业大学.2016

[6].曹萌萌.图的几种N（p，q）标号问题与图的两类染色问题[D].山东师范大学.2012

[7].于永.图的[r，s，t；f]-染色及（p，1）-全标号问题[D].山东大学.2012

[8].孙美姣.图的（p，1）-全标号及图的弱邻点可区分的染色问题[D].山东师范大学.2010

[9].马帅.特殊图类的标号染色[D].山东大学.2009

[10].刘晓晓.有邻域限制的图染色问题及图的L（2，1）—标号[D].山东师范大学.2009

标签：邻积可区别全染色;  反魔幻标号;  彩色匹配;