学位论文 > 优秀研究生学位论文题录展示

带有邻域限制的三类染色问题

作　者: 马迎雪
导　师: 孙磊
学　校: 山东师范大学
专　业: 应用数学
关键词: k-正常染色条件染色支撑树单射染色 L(2，1)-标号邻域限制标号
分类号: O157.5
类　型: 硕士论文
年　份: 2011年
下　载: 20次
引　用: 1次
阅　读: 论文下载

内容摘要

由于图论理论在现代应用数学中的重要作用以及计算机科学和组合优化的发展,图论作为数学科学中一门独立的学科飞速发展起来.图的染色问题是图论研究中一个非常活跃的领域,有着很好的理论探讨价值和实际意义.基于此,数学家们在传统的点染色,边染色的基础上添加各种限制,拓展出了许多新的染色分支.赖宏建等人于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),恰为其邻域限制标号的平凡下界.

全文目录

中文摘要  5-9
英文摘要  9-14
第一章引言  14-19
  1.1 基本概念与符号  14-15
  1.2 图的染色问题的发展及现状  15-19
第二章图的条件染色  19-26
  2.1 正常图的充分条件  19-21
  2.2 r-正常图的充分条件  21-23
  2.3 图的r-条件色数的一个上界  23-26
第三章图的单射染色  26-34
  3.1 图的单射染色的概念与发展现状  26-27
  3.2 围长不小于6的平面图的单射色数  27-34
第四章图的邻域限制标号问题  34-41
  4.1 图的邻域限制标号数的界  35-38
  4.2 特殊图类的邻域限制标号数  38-41
进一步研究的问题  41-42
参考文献  42-45
在学期间发表的学术论文  45-46
致谢  46

带有邻域限制的三类染色问题

内容摘要

全文目录

相似论文