图的2-距离染色

发布时间：2017-08-03 12:29

  本文关键词：图的2-距离染色

  更多相关文章： 2-距离染色 圈 最大度 平面图

【摘要】：本文主要研究有限无向图.图G的k-2-距离染色是指映射c：V(G)→{1,2,…,k},使得对G中满足0dG(u,v)≤2的点对u,v有c(u)≠c(u)称x2(G)=min{k|G有一个k-2-距离染色}为G的2-距离色数. 图G的一个列表配置L是指给G的每个顶点v∈V(G)分配一个可用色集L(v).设L是G的一个列表配置,若G的一个2-距离染色c对任意的v∈V满足c(v)∈L(v),则称c是G的一个L-2-距离染色.若对G的任意一个满足|L(v)|≥k的列表配置L,G都有一个L-2-距离染色,则称G是2-距离k-可选的,并称x2l(G)=min{k|G是2-距离k-可选的}为G的2-距离列表色数. 关于平面图的2-距离染色,1977年,Wegner提出了如下的一个猜想：对平面图G,若△(G)=3,则x2(G)≤7；若4≤△(G)≤7,则x2(G)≤△(G)+5；若△(G)≥8,则x2(G)≤[3/2；△(G)]+1. 本文分为三章,主要研究了不含特殊短圈的平面图和最大度小于等于5的图的2-距离染色.第一章介绍了一些基础定义和2-距离染色的研究现状,并给出了本文的主要结果.第二章主要研究了不含特殊短圈的平面图的2-距离染色.证明了：(1)若G是不含3-,4-,8-圈且△(G)≥14的平面图,则x2(G)≤△(G)+5.(2)若G是不含3-,5-圈和相交4-圈且△(G)≥12的平面图,则x2l(G)≤△+6.第三章主要研究了最大度小于等于5的图的2-距离染色.证明了：(1)若图G满足△(G)≤5且mod(G)18/7,则x2l(G)≤7.(2)若平面图G满足△(G)≤5,则下列结论成立：1)若g(G)≥5,则x2l(G)≤13；2)若g(G)≥6,则x2l(G)≤11；3)若g(G)≥7,则x2l(G)≤9；4)若g(G)≥8,则x2l(G)≤8.
【关键词】：2-距离染色 圈 最大度 平面图
【学位授予单位】：浙江师范大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：O157.5
【目录】：

• 摘要3-4
• ABSTRACT4-6
• 目录6-7
• 1 绪论7-13
• 1.1 基本概念7-8
• 1.2 2-距离染色的研究概况8-12
• 1.3 本文的主要结果12-13
• 2 不含特殊短圈的平面图13-39
• 2.1 不含3-,4-,8-圈的平面图13-27
• 2.2 不含3-,5-圈和相交4-圈的平面图27-39
• 3 最大度小于等于5的图39-58
• 3.1 △(G)≤5且mad(G)<18/739-44
• 3.2 △(G)≤5的平面图44-58
• 参考文献58-61
• 在学期间的研究成果及发表的论文61-62
• 致谢62-64

【参考文献】

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

1 谢朝宗;;马斯内版《玛侬》:大都会舞台上尽显巴黎社交生活[J];歌剧;2012年05期

，

本文编号：614429