限制染色论文-杨环

导读:本文包含了限制染色论文开题报告文献综述及选题提纲参考文献，主要关键词:广义(α,β)-边染色,广义(α,β)-边色数,路,圈

限制染色论文文献综述

杨环^[1]（2019）在《图的几类限制条件的边染色》一文中研究指出邻点可区别边染色、邻和可区别边染色与孪生边染色是叁种重要的限制条件边染色概念,它们分别是按“色集”、“色和”与“模色和”能够诱导出正常点染色的正常边染色.根据这叁种诱导方式,定义了叁类更一般的限制条件的边染色概念:“色集(α,β)-边染色”、“色和(α,β)-边染色”与“模色和(α,β)-边染色”,其中α和β为正整数.这三种限制条件的边染色统称为广义(a,b)-边染色.图G的k-色集(α,β)-边染色是指按色集能诱导出G的β-距离点染色的G的k-α-距离边染色,最小的k值称为G的色集(α,β)-边色数,记为ind_(a、β)~s(G).G的k-色和(α,β)-边染色是指按色和能诱导出G的β-距离点染色的G的k-α-距离边染色,最小的k值称为G的色和(α,β)-边色数,记为ind_(a、β)~t(G),其中颜色集合为[k].G的k-模色和(α,β)-边染色是指按模色和能诱导出G的β-距离点染色的G的k-α-距离边染色,最小的k值称为G的模色和(α,β)-边色数,记为ind_(a、β)~m(G),其中颜色集合为0{1,...,k-1}.主要研究了当α=β时特殊图类及其运算图的广义(α,β)-边染色问题,其中α为1或正偶数.主要内容如下:1.当(?)且(n)_(2k+1)=0时,得到了n阶路与圈的广义(2k,2k)-边色数.并对k=1的情形,给出了n阶路与圈的广义(2,2)-边色数.2.确定了两个路的笛卡尔积的广义(1,1)-边色数,并得到了2阶路与3n阶路的半强积的广义(2,2)-边色数.3.得到了无限路的笛卡尔积、直积的广义(1,1)-边色数.4.证明了两个图P_n(或C_n)与K_n的联的色集(1,1)-边色数与色和(1,1)-边色数均为2n.5.给出了两个图的冠积的色和(1,1)-边色数的一个上界,并证明这个上界对两个同构正则图的冠积是可达的.(本文来源于《西北民族大学》期刊2019-05-01）

范英英^[2]（2017）在《平面图的限制列表染色》一文中研究指出令G =(V,E)是一个图.图G的一个正常kk-点染色是指k种颜色对于G的各顶点的一个分配,满足任意两个相邻顶点得到不同的颜色.如果G有一个正常kk-点染色,那么称G是k-可染的.G的色数定义为最小的正整数kk值,并用χ(G)来表示.G的一个顶点色列表配置L是一个颜色集合簇,它指定G中每个顶点x 一个颜色集合L(x).如果G有一个正常的顶点染色π,使得对每个顶点x ∈ V,都有π(x)∈ L(x),那么称G为L-可染的或称π是G的一个L-染色.假若对每一个满足|L(x)| ≥ k的列表配置L,G都是L-可染的,那么称G是kk-列表可染的,或称k-可选的.G的选择数定义为使得G是k-可选的最小的正整数k值.在列表染色定义的基础上,Kratochvil,Tuza和Voigt于1998年首次提出了限制列表染色的概念.如果对于任意相邻顶点u和v均满足|L(u)∩ L(v)| ≤ d而且G是k-可选的,那么我们说G是(k,d)-可选的.着名的Thomassen定理说明了平面图是(5,5)-可选的.Kratochvil,Tuza和Voigt证明了平面图是(4,1)-可选的.之后Voigt构造了一类非(4,3)-可选的平面图.目前平面图的(4,2)-可选性仍未得到完全证实.由于平面图的3-可选性一直是图染色问题的热点与焦点,近年来,平面图的(3,1)-可选性问题引起了研究者的极大关注.本学位论文共分为叁章,主要围绕平面图的(3,1)-可选性问题展开研究,所得的结论改进了现有的一些结果.在第一章中,我们先给出本文所用到的基本概念,再简述相关领域的研究现状并呈现本文的主要结果.在第二章和第叁章中,我们摒弃了传统的权转移方法,运用经典的Thomassen列表色延拓的方法分别证明了以下两个结果:(1)若平面图G既不包含5-圈也不包含正常相邻的4-圈,则G是(3,1)-可选的.(2)若平面图G既不包含6-圈也不包含相邻的4-圈和5-圈,则G是(3,1)-可选的.(本文来源于《浙江师范大学》期刊2017-03-08）

陈丹丹^[3]（2016）在《图的带有路长限制的点染色研究》一文中研究指出图G的点染色是G的顶点集的一个剖分.如果G的顶点集V可以剖分成k个部分V1,V2,…,Vk,使得k∪i=1Vi=V,Vi∩Vj=0对任意i≠i成立,且对任意1≤i≤k,G[Vi]满足某种特定要求.若V1,V2,…,Vk是点独立集,则称这种染色是正常染色；若V1,V2,…,Vk不是点独立集,则称这种染色是非正常染色.如果图G可以用k种颜色正常染色,则称G为k可染的.令x(G)=min{k|G是k色可染的},称χ(G)为图G的点色数,有时简称为色数.论文第一章主要介绍了一些基本概念和符号,阐述了图的非正常点染色的历史及发展,本文中未加说明的术语和符号参见文献[1].定义1.2.1令G=(V,E)是一个图,图G的一种退化染色是把图G的顶点剖分成k个部分V1,V2,…,Vk,使得k∪i=1Vi=V,Vi∩Vj=0对任意i≠i成立,且对任意1≤i≤k,G[K]中所有顶点的度数不超过di,则称图G是(d1,d2,…,dk)可染的.这种非正常染色是对每个色类的点导出子图中顶点的度数做限制.1976年,Steinberg提出了如下猜想.猜想1.2.1[2]不含4-圈和5-圈的平面图是叁色可染的,即(0,0,0)-可染的.为了证明这一猜想,一些学者将染色推广到了退化染色,主要有以下结果.定理1.2.3 (1)[14]若图G为平面图,且不含相交叁角形和5-圈,则图G是(1,1,0)-可染的.(2)[15]若图G为平面图,且不含相交叁角形和5-圈,则图G是(2,0,0)-可染的.(3)[16]若图G为平面图,且不含邻接叁角形和5-圈,则图G是(1,1,1)-可染的.(4)[17]若图G为平面图,且不含4-圈和5-圈,则图G是(1,1,0)-可染的.(5)[18]若图G为平面图,且不含4-圈和5-圈,则图G是(3,0,0)-可染的.(6)[19]图G为平面图,且不含4-圈和6-圈,则图G是(1,1,0)-可染的.(7)[20]若图G为平面图,且不含4-圈和6-圈,则图G是(2,0,0)-可染的.当G[Vi]给定其它限制时,可以导出图G的几类其它染色.例如定义1.2.2定义的这种非正常染色.定义1.2.2 令G=(V,E)是一个图,如果图G的顶点可以剖分成k个部分V1,V2,…,Vk,使得k∪i=1Vi=V,Vi∩Vj=0对任意i≠i成立,且对任意1≤i≤k,G[Vi]为森林,满足上述条件的k的最小值称为图G的点荫度,记作va(G).孙磊老师在2015年提出了一种新的非正常染色,这种染色规定G[Vi]不含长度超过l(l≥0)的路Pl,这里l指路P的边数,具体定义如下定义1.2.3如果图G的顶点可以剖分成k个部分V1,V2,…,Vk,使得k∪i=1Vi= V,Vi∩Vj=0对任意i≠j成立,且Vi的导出子图G[Vi]不含长度超过l(l≥0)的路Bl,其中1≤i≤k,则称图G有一个Pl-染色(称作是Pl-可染的).使得图G有不含长度超过l(l≥0)的路Pl染色的最小剖分数k叫做图G的Pl-染色数,记作xpl(G).论文第二章主要研究了简单图的P2-染色,尤其是具有低最大度图的P2-染色,分别给出了△(G)≤3及△(G)≤4时,图G的P2-色数的上界,并且证明了这个上界是紧的.定理2.1.1对任意简单图G,若△(G)≤3,则χρ2(G)≤2.这个色数上界是紧的,因为任意一条路长超过2的路都必须至少用两个颜色来染.定理2.1.1'对任意简单图G,若△(G)≤3,可在多项式时间内找到一个图G的色数至多为2的P2—染色.定理2.2.1对任意简单图G,若△(G)≤4,则χρ2(G)≤3.定理2.2.1’对任意简单图G,若△(G)≤4,可在多项式时间内找到一个图G的色数至多为3的P2-染色.这个色数上界是紧的,比如如下定义的图GV(G)={vij|i=1,2,3;j=1,2,3};E(G)={vijvi(j+1)|i=1,2,3;j=1,2}∪{vk3vk1|k=1,2,3}.显然△(G)=4.定理2.2.2对于上述图G,有xp2(G)=3.论文第叁章主要研究了部分特殊图的P2-染色及Pl—染色.定理3.1对于n阶完全图G,有xp2(G)=[n/3].定义3.1对于任意图G=(V1,E1)和H=(V2,E2),笛卡尔乘积图定义如下V(G□H)=V1×V2={(vi,vj)|(?)ui∈V1,vj∈V2};E(G□H)={(u1,v1),(u2,v2)|v1=v2且(u1,u2)∈E1或u1=u2且(u1,u2)∈E2}.定理3.2对于任意n阶图G及有t个顶点的路Pt-1,若xpl(G)=k且k>2.l≥0,则xpl(Pt-1□G)=k.定理3.3对于任意n阶图G及有t个顶点的圈Ct,若xpl(G)=k且k≥3,l≥0,则xpl(Ct□G)=k.当χρl(G)=2时,我们有下述两个结论.定理3.4对于任意n阶图G及有2m个顶点的圈G2m,若xpl(G)=2,l≥0,则xpl(G2m□G)=2.定理3.5对于任意n阶图G及有2m1个顶点的圈G2m+1,若xpl(G)=2,l≥0,则xpl(G2m+1□G)≤3.(本文来源于《山东师范大学》期刊2016-04-10）

马迎雪^[4]（2011）在《带有邻域限制的叁类染色问题》一文中研究指出由于图论理论在现代应用数学中的重要作用以及计算机科学和组合优化的发展,图论作为数学科学中一门独立的学科飞速发展起来.图的染色问题是图论研究中一个非常活跃的领域,有着很好的理论探讨价值和实际意义.基于此,数学家们在传统的点染色,边染色的基础上添加各种限制,拓展出了许多新的染色分支.赖宏建等人于2006年在《离散数学》上提出了条件染色的概念并得到了一些结论,在《图的条件染色》一文中,他们提出并讨论了一些特殊图类的条件色数,般图的条件色数上界以及正常图的几个充分条件等.2002年,G.Hahn,J.Kratochvil, J.Siran,D.Sottean等人在《离散数学》上发表文章《图的单射色数》,在文中他们首次提出了单射染色.自此,在这个问题,特别是满足一定条件的平面图的单射色数方面,涌现出很多好的结果.2008年,孙磊,刘晓晓提出了邻域限制标号的概念,在刘晓晓的硕士毕业论文中,她研究了满足一定条件的图的邻域限制标号数下界,圈和树的邻域限制标号数以及邻域限制标号的几个性质等.这叁类染色问题都是带有邻域限制的染色问题.在本文第一章里,我们主要介绍了文章中涉及的一些基本概念与符号,描述了图的染色问题的发展及现状.本文未加说明的定义及符号参见[1].定义1图G的一个正常k-染色是一个映射c：V(G)→[k]使得相邻点获得的颜色不同.使G有一个正常染色的最小k值称为G的色数,记为χ(G).本文未加特殊说明的染色均指正常染色.定义2一个正常条件(k,r)-染色是一个映射c：V(G)→[k]使得：(1)若uv∈E(G),则c(u)≠c(v)；(2)对任意v∈V(G),｜c(N(v))｜≥min{｜N(v)｜,r}.使G有一个正常条件(k,r)-染色的最小k值称为G的条件色数,记为χr(G).定义3称一个图G是正常的,若χ2(G)=χ(G).类似的,称一个图G是r-正常的,若χr(G)=χ(G).在第二章中,我们主要研究了图的条件染色问题,给出了正常图及r-正常图的几个充分条件并改进了图的条件色数的上界.定理2.1.5令G为n(n≥3)个顶点的图,若δ(G)>「n/2」,则G是正常的.这个关于δ(G)的界是紧的.定理2.1.7令n=│V(G)│,若G中任意两个相邻点的度和大于n,则G是正常的.这个度和的界是紧的.定理2.1.9若G为满足任意度大于1的点都在叁角中的图,则G的线图L(G)是正常的.此外,若n≡0(mod3)且n≡1(mod2),则圈G的线图也是正常的.定理2.2.2G为n个顶点的图,r≥2是整数,若δ(G)≥[(r-1)n/r]+1,则G是r-正常的.这个关于δ(G)的界是紧的.定理2.2.3设G为n个顶点的连通图,若对任意其导出子图连通的r个顶点,其度和大于n(r-1),则G是r-正常的.这个关于度和的界是紧的.定理2.3.2χr(G)≤△2+1.等号成立当且仅当G为Moore图.定理2.3.4若G不含5-圈且△(G)≥2,则χr(G)≤Δ2.定义4称图的一个染色c：V(G)→{1,2,…,k}是单射的,若图中任一顶点的邻点的颜色两两不同,即若x,y∈V(G)在G中有公共邻点,则c(x)≠c(y).使G存在一个单射染色的最小k值称为G的单射色数.在第叁章中,我们主要研究了图的单射染色问题,介绍了在研究平面图中用到的一些特殊的概念,符号以及部分已有的研究成果.同时,我们给出了围长不小于6时图的单射色数的上界以及△=8和△=9时图的单射色数的特殊性质.定理3.2.5令G是围长为g(G)≥6,最大度为△的平面图,(1).χi(G)≤△+2；(2).若△=8时χi(G)≤△+1,则对任意最大度的图G有χi(G)≤△(G)+1.(3).若△=9时χi(G)=△,则对任意最大度的图G有χi(G)=△(G).定义51对于整数k>0,图的邻域限制标号是一个映射c：V(G)→{0,1,…,k},使得:(1)对任意u,v∈V(G),若d(u,v)=1,则│c(u)-c(v)│≥1；(2)对任意u,v∈V(G),若存在ω∈V(G)使得u,v∈NG(ω),则│c(u)-c(v)│≥2.满足上述条件的最小k值称为邻域限制标号数,记为L1,2(G).在第四章中,我们主要研究了图的邻域限制标号问题.对于图的邻域限制标号数,易见其有平凡的上下界2(Δ-1)≤L1,2(G)≤2(n-1).在本章中我们给出了图的邻域限制标号数达到其平凡上下界的充要或充分条件,改进了非K2图的邻域限制标号数的上界并讨论了几个特殊图类的邻域限制标号数.定理4.1.2图G的邻域限制标号数L1,2(G)=2(n-1)(n=│V(G)│)当且仅当图G为完全图或者G的直径为2且任意边含于叁角中.定理4.1.3图G的邻域限制标号数L1,2(G)=2(Δ-1)则图G满足以下几种结构特点：(1)任意两个最大度点不相邻；(2)最大度点的邻点中至少存在两个点与其他邻点不相邻；(3)若两个最大度点距离为2且邻点相同,则至少有3个邻点彼此不相邻.定理4.1.5若G不是K2,则L1,2(G)≤2Δ2-2Δ.在此条件下这个界是最好的.称一个图s1(G)[5]为图G的第一剖分图,若此图是由G中的每条边剖分一次得到的.直观的理解,第一剖分图就是用一条长为2的路代替原图中的每条边所得到的图形.令G=(V(G),E(G)),V(G)={v1,v2,…,vn},G的M-构造图M(G)的点集和边集是如下定义的：点集V(M(G))={v1,v2,v3,…,v。,u1,u2,u3,…,un,v},边集E(M(G))=E(G)∪{uiv│i=1,2…,n}∪{uivj│vivj∈E(G)}.定理4.2.2令n=│V(G)│,若G的最大度为△且G不是完全图,S1(G)为G的第一剖分图,则2(Δ-1)≤L1,2(S1(G))≤2Δ-1；若G是完全图则L1,2(S1(G))=2Δ.定理4.2.4令n=│V(G)│≥5,M(G)为G的M-构造图,若G的最大度Δ≤(?),则L1,2(M(G))=2(n-1),恰为其邻域限制标号的平凡下界.(本文来源于《山东师范大学》期刊2011-04-10）

周燕^[5]（2011）在《限制边的点染色》一文中研究指出本文考虑的图无特别声明均为简单无向有限图.本文讨论了图的消染色和点染色的推广限制边的点染色.Pn为长度为n-1的路,Kn为具有n个端点的完全图,Kn,n表示完全二部图,G∨H表示图G和图H的并图,G=Km(n)表示一个完全m部图且每部分的顶点数均为n.图G的消色数α(G)是指在图G的正常点染色中最大的颜色数满足顶点的任意俩个颜色类中至少有一条边相连.图G的伪染色是指在G的点染色中相邻的俩点可以染同色.图G的伪完全染色指在G的顶点的伪染色中,任意一对不同的颜色对在G中至少存在一条边其端点用这对颜色对着色.图G的伪消染色数ψ(G)指图G的伪完全染色中使用的最多颜色数.图G的限制边的点染色是指对图G的顶点进行伪完全染色,使得任意一对染色对至少有k条边相连.ψk(G)表示图G的限制边的染色数.当k=1时,限制边的点染色为图的伪消染色.本文主要证明了以下结论：定理1对任意自然数l,l=2k+1,存在路Pn满足ψ2(Pn)=2k+ 1,min|V(Pn)|=2k(2k+1)+1.推论1对路Pn继续延长得到路P*满足|V(P*)|=mk(2k+1)+1,对延长的部分进行同样的着色,则路P*满足ψm(P*)=2k+1且路P*是满足ψm(P)=2k+1的最短路,每对色类只出现m次,起末端点染同色.定理2对自然数t,t=2k,存在路Pn满足ψ2(Pn)=2k,min|V(Pn)|= 2k(2k-1)+1.推论2依次对P2k2延长染色,可得到路P满足ψm(P)=2k,且min|V(P)|=tA(?)+1,m=2t时,此时每对颜色类只出现m次,且起末端点染同色；min|V(P)|=(tA(?)+1)+(2k2-1),m=2t+1时,此时每对颜色类出现m次或m+1次.定理3ψ2(Kn)=[n/2],即n=2k+1时,ψ2(kn)=k+1;n=2k时,ψ2(kn)=k.定理4ψm(kn)=(?)或者ψm(kn)=(?)(m≥3).定理5ψm(kn,n)=(?)或者ψm(Kn,n)=(?)(m≥2)定理6G是最大度为△的简单图,且|V(G)|=p,则P≥n(?),n=ψm(G).定理7 G=K3(n)(一个完全叁部图且每部分的顶点数均为n)则ψ2(G)=(?).定理8 G=Km(n)则ψ2(G)=[mn/2].定理9令3≤l1≤l2≤…≤lk是正整数且∑ik=1li=p.如果k≤(?)p/2,则ψ(Cl1∪Cl2∪…∪Clk)=ψ(Cp).定理10对于绝大部分整数k,有ψ(kC4)=ψ(C4k).(本文来源于《山东大学》期刊2011-03-28）

张志芳^[6]（2010）在《关于若干特殊图的限制染色》一文中研究指出G=(V(G), E(G))是简单图，给定非负整数d,图G的k-(d, 1)一全标号是一个映射f:V(G) U E(G)→{0，1，....k}，使得:对任意两个相邻顶点ui,uj,有f(ui)≠f(uj);对任意两条相邻的边ei,ej，有f(ei)≠(ej);对任意一对关联的点和边ui≠V(G)，ej≠E(G)有f(yu)-f(ej)≠d.(d,1)-全标号的跨度是指两个标号差的最大值，图G的(d, 1)-全标号的最小跨度叫图G的(d, 1)-全标号数，记作≠Td(G).针对两类直积图Pm,×Cn,，和Pm,×Kn，研究了(d, 1 )-全标号问题，完全确定了其(d, 1)-全标号数.另外得到了偶完全图K2n，的带限制条件的[r,s,1]-染色，其中r≥2且s≥r+2.(本文来源于《河北工业大学》期刊2010-09-01）

刘晓晓^[7]（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）

赵聪俐^[8]（2008）在《一种带有限制的缺陷染色的研究》一文中研究指出设G是一个图.如果图G的顶点能够用k个颜色来染,通过这种染色使得它的每个顶点至多有d个染相同颜色的顶点和它相邻,而且这样的顶点最少为t个,那么我们称图G是(k,d,t)*-可染的.在这个新定义的基础上,本文主要给出了几种特殊图类的一些结果和它们的证明,诸如圈、完全图等.另外,通过"带有限制的缺陷染色"这个新定义提出了对平面图"四色问题"的一点新看法,对"四色定理"的证明可能会有所帮助.(本文来源于《数学学习与研究(教研版)》期刊2008年11期）

韩淑芹^[9]（2007）在《图的邻点可区别全染色和有全色子图限制的染色问题》一文中研究指出染色问题是图论研究的经典领域，它源自于四色定理的研究，是图论研究中一个很活跃的课题。随着染色问题在现实中被广泛应用，各类染色问题被相继提出并加以发展、应用。图G的一个(正常)k-染色是将k种染色分配给G的顶点集V(G)，使得相邻两顶点的颜色不同。定义色数为：x(G)=min{k|图G有k-染色}。类似的，图G的一个(正常)k-边染色是将k种染色分配给G的边集E(G)，使得有公共端点的两边的颜色不同。边色数x′(G)=min{k|图G有k-边染色}。全染色的概念是对点染色和边染色的推广，是图论染色的一个传统问题，由Vizing(1964)和Behzad(1965)各自独立提出的。图的全染色是对图的点，边进行染色，使得相邻或相关联的两元素染色不同。图的全色数xT(G)=min{k|图G有一个k-全染色}。在全染色的基础上，张忠辅提出了邻点可区别的全染色的概念并给出了相应的猜想和两个引理。张忠辅定义的邻点可区别的全染色如下：设G(V，E)为阶不小于2的简单连通图，k为正整数，令映射f：V(G)∪E(G)→{1，2，…，k}。对任意u∈V(G)，如果(1)对任意uv，vw∈E(G)，u≠w，有f(uv)≠f(vw)。(2)对任意uv∈E(G)，有f(u)≠f(v)，f(u)≠f(uv)，f(uv)≠f(v)。则称f为图G的一个k-全染色，简记为k-TC。若还满足(3)对任意uv∈E(G)，C(u)≠C(v)，其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}。那么称f为图G的一个k-邻点可区别全染色，简记为k-AVDTC。图G的全色数xT(G)(或记为x″(G))=min{k|图G有k-全染色}。图G的邻点可区别的全色数xat(G)=min{k|图G有k-AVDTC}。张忠辅给出了关于邻点可区别全染色的两个引理：对任意阶为n(n≥2)的简单连通图G，邻点可区别全色数xat(G)存在，并且xat(G)≥△(G)+1。若图G(V，E)有两个相邻的最大度点，则有xat(G)≥△(G)+2。张忠辅在文献中给出了邻点可区别全色数猜想：对任意阶为n(n≥2)的简单连通图G，有xat(G)≤△(G)+3。确定一任意给定图的邻点可区别全色数是NP-困难的。目前关于路，圈，完全图，完全二部图，星，扇，轮，树等特殊图的邻点可区别全色数已给出。另外上述特殊图的Mycielski图，联图和乘积图的邻点可区别全色数已有一些结果。同时，Petersen图，Heawood图，Thomassen图的邻点可区分全色数也已得到结果。1880年，边染色的概念被提出，在边染色问题的研究中有着名的四色定理。1964年，Vizing得出一个重要的定理即对任意的简单图G，有△(G)≤x′(G)≤△(G)+1。1974年，R．P．Gupta对边覆盖染色进行了研究。图G的边覆盖染色是对图G的所有边进行染色使得每种颜色在每个顶点上至少出现一次。满足图G有一个k-边覆盖染色的最大正整数k称为图G的边覆盖色数，记为x′_c(G)。同年，Gupta证明了对任意的简单图G，有δ(G)-1≤x′_c(G)≤δ(G)。若x′_c(G)=δ(G)，则称G是第一类的。若x′_c(G)=δ(G)-1，则称G是第二类的。刘桂珍老师及苗连英，宋惠敏等对图的边覆盖染色进行了进一步的研究并取得了丰硕的成果。2006年，孙磊老师受边覆盖染色的启发提出了全色极大团染色的概念。全色极大团染色是对图G的顶点进行染色，使得G的每个极大团所有颜色均出现。满足图G有一个k-全色极大团染色的最大正整数k称为图G的全色极大团色数，记为xmaxcT(G)。显然有xmaxcT(G)≤min{|H||H为G的极大团}。本文一部分主要探讨了轮，完全图的Hajós sum的邻点可区别全色数。另外还得到了特殊图P_n~k，花G的邻点可区别全色数。另一部分讨论了特定条件下全色极大团染色与边覆盖染色的等价性，给出了联图，复合图，笛卡尔乘积图，外平面图的全色极大团色数，并给出了K_n-M，C_n，Mycielski图，类Mycielski图的全色极大团色数。在本文中，我们主要得到结论如下：两个点不交的图G_1和G_2的Hajós sum G=(G_1，x_1y_1)+(G_2，x_2y_2)是由G_1∪G_2粘合x_1，x_2为一个点，删去边x_1y_1，x_2y_2增加边y_1y_2所得。其中x_1y_1∈E(G_1)，x_2y_2∈E(G_2)。令W_n=K_1∨C_n，V(W_n)={v_1，v_2，…，v_n，v_0)，E(W_n)={v_iv_(i+1)|i=1，2，…，n；v_(n+1)=v_1}∪{v_0v_i|i=1，2，…，n}，W′_n为W_n的复制。定理2．1．1 Hajós sum W_n~*=(W_n，v_1v_2)+(W′_n，v′_1v′_2)，粘合v_1，v′_1为一个点v_1，则定理2．1．2 Hajós sum G=(W_n，v_0v_1)+(W′_n，v′_0v′_1)，粘合v_0，v′_0为一个点v_0，则xat(G)=2n-1。定理2．1．3 Hajós sum G=(K_m，v_1v_2)+(K_n，v′_1v′_2)，粘合v_1，v′_1为一个点v_1，则在含有n个顶点的路P_n上，当且仅当两点距离为k时添加一条边，所得的图称为P_n~k图。定理2．2．1对图P_n~k，k=[n/2]，有Xat(P_n~k)=5。K_n是具有n个顶点v_1，…v_n的完全图，在K_n的每个顶点v_i上悬挂m_i(1≤i≤n)个点v_(i1)，…，v_(imi)，这m_i个点形成一条路v_(i1)v_(i2)…v_(imi)，如此得到花G。定理2．2．2对花G，不妨设m_s=max_k=1，2…n m_k，有对任意的图G，其线图L(G)的顶点集为E(G)，两点之间有边当且仅当在图G中两边相邻。对任意的图G，其全图T(G)的顶点集为V(G)∪E(G)，两元素间有边当且仅当在图G中两元素相邻或相关联。记p=min{|G′||G″为G的极大团}。q=min{|H′||H′为H的极大团}。定理3．1．1若存在H使G=L(H)且p≥4。则图G的全色极大团染色等价于图H的边覆盖染色。Gupta定理的内容是对任意的简单图G。有δ(G)-1≤x′_c(G)≤δ(G)。推论3．1．2 Gupta定理等价于下面两种情形：(1)若存在H使G=L(H)且p≥4，则有p-1≤xmaxcT(G)≤p。(2)若存在H使G=T(H)且p≥4，则有p-1≤xmaxcT(G)≤p。M是完全图K_n的某一匹配，则K_n-M的所有极大团点数相同，均为n-2|M|+|M|=n-|M|，且K_n-M的每个极大团的点集形式为V(K_n)＼V(M)与|M|个点的并集，这|M|个点是从M的每个匹配边连结的两点中任意一点组成的。定理3．1．3完全图K_n，N(?)E(K_n)且δ(K_n-N)≥n-2，则xmaxcT(K_n-N)=n-|N|。定理3．1．4 G=C_n，则两个图G和H的联图G∨H定义为：V(G∨H)=V(G)∪V(H)，E(G∨H)=E(G)∪E(H)∪{uv|u∈V(G)。v∈V(H)}。定理3．1．5对任意简单连通图G，H，有xmaxcT(G∨H)=xmaxcT(G)+xmaxcT(H)。两个图G和H的复合图G[H]定义为：它的顶点集为V(G)×V(H)，其中两个顶点(u，v)，(u′，v′)相邻当且仅当或者uu′∈E(G)，或者u=u′，vv′∈E(H)。定理3．1．6图G，H分别满足xmaxcT(G)=p，xmaxcT(H)=q，则有xmaxcT(G[H])=xmaxcT(G)xmaxcT(H)。并不是对所有的简单连通图G，H均有xmaxcT(G[H])=xmaxcT(G)xmaxcT(H)。例如：G=P_n，H=C_(2m+1)，而xmaxcT(P_n[C_(2m+1])=3≠2×1。对于图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)=(u_i，v_j)，1≤i≤m，1≤j≤n}，E(G×H)={w_(ij)w_(kl)，i=k和v_jv_l∈E(H)或j=l和u_iu_k∈E(G)}。定理3．1．7若p-1≤xmaxcT(G)≤p，q-1≤xmaxcT(H)≤q，则有xmaxcT(G×H)=min{xmaxcT(G)，xmaxcT(H)}。我们称由Mycielski作图法得到的图为Mycielski图。给定图G，其顶点集V={v_1，v_2，…，v_n}。图G的Mycielski图(记为M(G))定义为：顶点集V(M(G))=V∪{v′_1，v′_2，…，v′_n，w}，边集E(M(G))=E(G)∪{v_iv′_j|v_iv_j∈E(G)，i，j=1，…，n}∪{v′_iw|i=1，…，n}。定理3．2．1对任意简单连通图G，均有xmaxcT(M(G))=1。定理3．2．2对任意简单连通图G，令u(G)=M(G)-w，则xmaxcT(u(G))=xmaxcT(G)。给定图G，顶点集为V={v_1，v_2，…，v_n}。图G的类M构造图(记为S(G))定义如下：V(S(G))=V(G)∪V(G′)∪{w}，G′为G的复制。边集E(S(G))=E(G)∪E(G′)∪{v_iv′_i|v_i∈V(G)，i=1，2，…，n}∪{v_iv′_j|v_iv_j∈E(G)，i，j=1，2，…n}∪{v′_iw|i=1，2，…，n}。对图S_m(G)定义为：S_1(G)=S(G)。V(S_m(G))=V(G)∪V(G′)∪V(G″)∪…∪V(G~((m))∪{w}，E(S_m(G))=E(G)∪E(G′)∪E(G″)∪…∪E(G~((m)))∪{v_i~((j))v_i~((j+1))|v_i∈V(G)，i=1，2，…，n；j=0，1，…，m-1；v_i~((0))=v_i}∪{v_i~((k))v_j~((k+1))|v_iv_j∈E(G)，i，j=1，2，…，n；k=0，1，…，m-1}∪{v_i~((m))w|v_i∈V(G)，i=1，2，…，n}。定理3．2．3对任意简单连通图G，有xmaxcT(S(G))=xmaxcT(G)+1。推论3．2．4令S_0(G)=G∨{w}，则有xmaxcT(S_0(G))=xmaxcT(G)+1。定理3．2．5对任意简单连通图G，有xmaxcT(S_m(G))=xmaxcT(G)+1。定理3．2．6若G为外平面图且p=2，则定理3．2．7若G为外平面图且p=3，则xmaxcT(G)=3。(本文来源于《山东师范大学》期刊2007-04-10）

倪亚洲^[10]（2006）在《有限制条件的平面图的均匀染色》一文中研究指出设G是一个图，图G的一个顶点染色是指k种颜色1，2，…，k对G的各个顶点的一个分配，且G的任意两个相邻顶点都分配到不同的颜色，令V~i记颜色为i的顶点的集合，如果图G的一个顶点染色对所有的i，j满足‖V~i|-|V~j‖≤1，那么称这一染色为图G的一个均匀k-染色，图G具有均匀k-染色的最小整数k称为G的均匀色数，记为Xe(G)。 W．Meyer[1]证明了：任意树T都存在均匀(「Δ(T)/2(?)+1)-染色。并提出了以下猜想： 猜想1：对于任意一个既不是完全图也不是奇圈的连通图G，有Xe(G)≤Δ(G)。 Hajnal和Szemerédi[2]较早地证明了：任意图G，对于任意的整数k≥Δ(G)+1，都存在均匀k-染色。Yap和Zhang[10]证明了：最大度Δ≥13的任意平面图G，对任意整数m≥Δ，都存在均匀m-染色。 Lih和Wu[6](Yap[12])证明了：如果图G是一个连通的二部图，且不是完全二部图K_(2m+1，2m+1)，m≥0，那么G存在均匀Δ-染色。基于这一结果，Chen，Lih和Wu提出了以下猜想： 猜想2：如果图G是一个既不是完全图，奇圈又不是完全二部图K_(2m+1，2m+1)，m≥0的连通图，那么G存在均匀Δ-染色。 Yap和Zhang在[7]中证明了最大度Δ≥3的连通的外平面图G存在均匀Δ-染色；在[9]中证明了：最大度Δ≥|G|/3+1的图G存在均匀Δ-染色。 本论文首先叙述了与均匀染色相关的一些背景知识，第二，叁，四章分别详细地论述了以下结果： 1．任意一个阶为n的平面图G，如果围长g≥4，那么有e≤2n-4，且δ≤3；如果g≥ 6，那么有e≤3/2(n-2)，且δ≤2。我们可以证明，如果Δ≥9和g≥4，或者Δ≥8和g≥6，那么平面图G存在均匀Δ-染色；(本文来源于《山东大学》期刊2006-04-18）

限制染色论文开题报告

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

此处内容要求：

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

写法范例：

令G =(V,E)是一个图.图G的一个正常kk-点染色是指k种颜色对于G的各顶点的一个分配,满足任意两个相邻顶点得到不同的颜色.如果G有一个正常kk-点染色,那么称G是k-可染的.G的色数定义为最小的正整数kk值,并用χ(G)来表示.G的一个顶点色列表配置L是一个颜色集合簇,它指定G中每个顶点x 一个颜色集合L(x).如果G有一个正常的顶点染色π,使得对每个顶点x ∈ V,都有π(x)∈ L(x),那么称G为L-可染的或称π是G的一个L-染色.假若对每一个满足|L(x)| ≥ k的列表配置L,G都是L-可染的,那么称G是kk-列表可染的,或称k-可选的.G的选择数定义为使得G是k-可选的最小的正整数k值.在列表染色定义的基础上,Kratochvil,Tuza和Voigt于1998年首次提出了限制列表染色的概念.如果对于任意相邻顶点u和v均满足|L(u)∩ L(v)| ≤ d而且G是k-可选的,那么我们说G是(k,d)-可选的.着名的Thomassen定理说明了平面图是(5,5)-可选的.Kratochvil,Tuza和Voigt证明了平面图是(4,1)-可选的.之后Voigt构造了一类非(4,3)-可选的平面图.目前平面图的(4,2)-可选性仍未得到完全证实.由于平面图的3-可选性一直是图染色问题的热点与焦点,近年来,平面图的(3,1)-可选性问题引起了研究者的极大关注.本学位论文共分为叁章,主要围绕平面图的(3,1)-可选性问题展开研究,所得的结论改进了现有的一些结果.在第一章中,我们先给出本文所用到的基本概念,再简述相关领域的研究现状并呈现本文的主要结果.在第二章和第叁章中,我们摒弃了传统的权转移方法,运用经典的Thomassen列表色延拓的方法分别证明了以下两个结果:(1)若平面图G既不包含5-圈也不包含正常相邻的4-圈,则G是(3,1)-可选的.(2)若平面图G既不包含6-圈也不包含相邻的4-圈和5-圈,则G是(3,1)-可选的.

（2）本文研究方法

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

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

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

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

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

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

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

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

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

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

限制染色论文参考文献

[1].杨环.图的几类限制条件的边染色[D].西北民族大学.2019

[2].范英英.平面图的限制列表染色[D].浙江师范大学.2017

[3].陈丹丹.图的带有路长限制的点染色研究[D].山东师范大学.2016

[4].马迎雪.带有邻域限制的叁类染色问题[D].山东师范大学.2011

[5].周燕.限制边的点染色[D].山东大学.2011

[6].张志芳.关于若干特殊图的限制染色[D].河北工业大学.2010

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

[8].赵聪俐.一种带有限制的缺陷染色的研究[J].数学学习与研究(教研版).2008

[9].韩淑芹.图的邻点可区别全染色和有全色子图限制的染色问题[D].山东师范大学.2007

[10].倪亚洲.有限制条件的平面图的均匀染色[D].山东大学.2006

标签：广义(α;  β)-边染色;  β)-边色数;  路;  圈;