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{dG（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

分类: 基础科学

专业: 数学

单位: 浙江师范大学

分类号: O157.5

DOI: 10.27464/d.cnki.gzsfu.2019.000008

总页数: 111

文件大小: 2374K

下载量: 20

相关论文文献

• [1].关于Kneser图的一个分数染色性质[J]. 甘肃高师学报 2016(12)
• [2].图的点可区别的分数边染色数[J]. 数学的实践与认识 2017(19)
• [3].站在多维的角度看世界[J]. 数字印刷 2018(07)
• [4].伪-海临图的群色数[J]. 赤峰学院学报(自然科学版) 2016(17)
• [5].扇、轮和完全图的r(2)点色数[J]. 甘肃联合大学学报(自然科学版) 2011(02)
• [6].两类循环图的均匀色数[J]. 嘉兴学院学报 2011(03)
• [7].图乘积的分数色数[J]. 泰山学院学报 2011(03)
• [8].边共色数下图的分类问题[J]. 长春工业大学学报(自然科学版) 2011(06)
• [9].联图的星色数[J]. 黑龙江科技学院学报 2011(06)
• [10].图的b-边染色数及b-边连续性研究[J]. 吉林化工学院学报 2010(04)
• [11].θ-图的对策着色和对策色数[J]. 中北大学学报(自然科学版) 2009(01)
• [12].两种特殊冠图的相关分数色数研究[J]. 西安文理学院学报(自然科学版) 2009(01)
• [13].升级手机的四大误区[J]. 广西质量监督导报 2009(05)
• [14].循环图的均匀色数[J]. 吉林师范大学学报(自然科学版) 2009(03)
• [15].单圈图的2-距离色数[J]. 甘肃科学学报 2009(03)
• [16].弱直积图的2-距离色数[J]. 兰州理工大学学报 2009(05)
• [17].几种特殊图形的分数色数研究[J]. 山西师范大学学报(自然科学版) 2008(04)
• [18].两类特殊超图的分数色数[J]. 昆明学院学报 2008(04)
• [19].与图的顶点染色数有关的几个问题[J]. 高师理科学刊 2016(03)
• [20].几类特殊图的条件色数[J]. 山东科学 2012(04)
• [21].球面经纬线图的分数色数[J]. 山西大同大学学报(自然科学版) 2010(01)
• [22].完全立方Halin图的2-距离着色[J]. 重庆工商大学学报(自然科学版) 2010(02)
• [23].广义θ-图的分数关联色数[J]. 重庆师范大学学报(自然科学版) 2010(06)
• [24].图的星色数的两个结果[J]. 天津科技大学学报 2010(05)
• [25].图的圆色数的一些结果(英文)[J]. Journal of Southeast University(English Edition) 2008(02)
• [26].竞赛图弧色数的上界[J]. 运筹学学报 2015(02)
• [27].Thomas数组的再发现[J]. 数学学习与研究 2019(20)
• [28].几类平面图的集合色数[J]. 西昌学院学报(自然科学版) 2011(02)
• [29].特殊平面图的集合色数[J]. 科技信息 2011(22)
• [30].两类齿轮图的分数色数[J]. 青岛理工大学学报 2011(04)

标签：标号论文;  动态染色论文;  平面图论文;  围长论文;  最大平均度论文;