图的距离为2的点可区别边染色

发布时间：2017-08-27 08:10

  本文关键词：图的距离为2的点可区别边染色

  更多相关文章： 距离为2的点可区别边染色 哈林图 外平面图 单圈图

【摘要】：图G的正常κ边染色是指存在一个映射φ:E(G)→｛1,2,…,k),使得相邻的边e和e,满足φ(e)≠φ(e')令Cφ(v)表示与点v相关联的边的颜色所构成的颜色集合,即Gφ(v)={φ(uv)|uv∈E(G)｝图G的距离为2的点可区别边染色是指,G的一个正常边染色满足对任意的两个距离为2的顶点u和v,都有Cφ(u)≠Cφ(v)图G的距离为2的点可区别边色数Χ'd2(G)是指G有一个距离为2的点可区别κ-边染色的最小k值.图的距离为2的点可区别边染色是r-强边染色的一种特殊情形.图的r-强边染色是由Akbari等人和Zhang等人在2006年分别独立提出的.设r≥1是一个整数,图G的r-强边色数Χ's:(G,r)是指G的一个正常边染色φ满足对任意两个顶点u和v,若d(u,v)≤r,都有Cφ(u)≠Cφ(v)的最小颜色数.若r=1,则Χ's:(G,1)=Χ'a(G),Χ'a(G)被称为邻点可区别边色数.邻点可区别边染色最早是由Zhang,Liu和Wang在2002年提出的,他们猜想：若G是一个|V(G)|≥6的连通图,则有Χ'a:(G)≤△+2. Balister等人证明了猜想对二部图和最大度不大于3的图是成立的Hatami运用概率方法证明了对每一个△1020的图G,都有Χ'a:(G)≤△+300.Akbari,Bidkhori和Nosrati证明了对每一个图G,都有Χ'a(G)≤3△.随后Wang等人将这个界进行了改进,证明了对任意的图G,Χ'aG)≤2.5△.本学位论文主要研究了图的距离为2的点可区别边染色问题,共分四章.在第一章中,介绍了基本概念和相关领域的研究现状,并且呈现了本文的主要结果.在第二章中,研究了特殊图类的距离为2的点可区别边染色,确定了一些简单图类、单圈图以及两类积图的距离为2的点可区别边色数.在第三章中,研究了哈林图的距离为2的点可区别边染色,证明了哈林图的距离为2的点可区别边色数的上界是△+2.在第四章中,研究了外平面图的距离为2的点可区别边染色,先证明了外平面图的距离为2的点可区别边色数的上界是2△,随后证明将上界改进到了△+8,最后证明了一类特殊外平面图的距离为2的点可区别边色数的上界是△+2.
【关键词】：距离为2的点可区别边染色 哈林图 外平面图 单圈图
【学位授予单位】：浙江师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 摘要3-4
• Abstract4-8
• 第一章 绪论8-16
• 1.1 基本概念8-9
• 1.2 点可区别边染色的研究概况9-14
• 1.3 本文主要结果14-16
• 第二章 特殊图类的距离为2的点可区别边染色16-38
• 2.1 简单图类的距离为2的点可区别边色数16-19
• 2.2 单圈图的距离为2的点可区别边色数19-24
• 2.3 两类积图的距离为2的点可区别边色数24-38
• 第三章 哈林图的距离为2的点可区别边染色38-50
• 3.1 预备引理38-45
• 3.2 主要结论及证明45-50
• 第四章 外平面图的距离为2的点可区别边染色50-92
• 4.1 一般上界2Δ50-54
• 4.2 改进的上界Δ+854-71
• 4.2.1 Δ≥5的外平面图55-65
• 4.2.2 Δ≤4的外平面图65-71
• 4.3 一类特殊外平面图的上界Δ+271-92
• 4.3.1 Δ≤3的情形71-76
• 4.3.2 上界Δ+2及其证明76-92
• 参考文献92-96
• 攻读学位期间取得的研究成果96-98
• 致谢98-100

【相似文献】

中国期刊全文数据库 前10条

1 孔立,倪亚洲;双外平面图的边染色[J];山东教育学院学报;2004年06期

2 孔立;双外平面图的边面染色[J];烟台师范学院学报(自然科学版);2005年02期

3 刘广德;;双外平面图点染色的一个结果[J];科技信息(学术研究);2008年27期

4 冯纪先;;最大外平面图和最大平面图的性质[J];高等数学研究;2013年04期

5 朱秉寰;;可外平面图的深探特性[J];优选与管理科学;1986年03期

6 韩培友,董桂云;关于外平面图的局部调和着色[J];北京邮电大学学报;1995年01期

7 李敬文，，刘林忠，张忠辅;外平面图结构性质的若干问题[J];佛山大学学报;1996年06期

8 张苏梅;外平面图的边面列表染色[J];山东农业大学学报;1998年01期

9 王骁力,张苏梅,李涛;外平面图的结构性质及在边着色上的应用[J];宝鸡文理学院学报(自然科学版);1998年03期

10 李涛,王骁力;外平面图的边列表染色[J];南都学坛;1998年03期

中国重要会议论文全文数据库 前2条

1 冯纪先;;最大外平面图G_(MO)的度[A];第十九届电工理论学术年会论文集[C];2007年

2 冯纪先;;标定的最大外平面图G_(MO)的数目[A];第十六届电工理论学术年会论文集[C];2004年

中国硕士学位论文全文数据库 前10条

1 刘维;外平面图的列表着色[D];华中师范大学;2012年

2 王二燕;2-连通外平面图的r-hued染色和不含邻接三角形的1-平面图的无圈边染色[D];中国矿业大学;2016年

3 王琰雯;图的距离为2的点可区别边染色[D];浙江师范大学;2016年

4 刘广德;双外平面图的点染色[D];山东大学;2008年

5 孔立;双外平面图的染色问题[D];山东大学;2005年

6 单伟;几类图的双约束边染色问题[D];山东大学;2008年

7 邵泽玲;外平面图的松弛竞赛色数[D];河北工业大学;2003年

8 方峻峰;平面图染色问题的研究[D];山东科技大学;2003年

9 张少君;图的若干特殊正常全染色[D];西北师范大学;2006年

10 许丰伟;图的完全可定向性[D];浙江师范大学;2010年

本文编号：745052