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

图的邻点可区别全染色和边染色

作　者: 王艺桥
导　师: 卜月华
学　校: 浙江师范大学
专　业: 运筹学与控制论
关键词: 图邻点可区别边色数邻点可区别全色数最大度
分类号: O157.5
类　型: 硕士论文
年　份: 2009年
下　载: 60次
引　用: 0次
阅　读: 论文下载

内容摘要

图的染色历来是图论研究的重要内容。本硕士论文研究了图的邻点可区别边染色和邻点可区别全染色.这两个概念是对传统的图的边染色和全染色的推广,在频道设计等领域有重要应用,近几年来得到了广泛研究。设χ′_α（G）,χ″_α（G）,Δ（G）和g（G）分别表示一个图G的邻点可区别边色数、邻点可区别全色数、最大度和围长。本硕士论文共分5章。在第1章,我们介绍了文中所用的概念和记号,概述了图的邻点可区别边染色和全染色的最新研究进展。在第2章,我们完全刻画了外平面图的邻点可区别全色数.证明了:若G是一个Δ（G）≥3的外平面图,则Δ（G）+1≤χ″_α（G）≤Δ（G）+2;且χ″_α（G）=Δ（G）+2当且仅当G含有两个相邻的最大度点。在第3章,我们研究了最大平均度小于3的图的邻点可区别全染色问题。确定了g（G）≥6和Δ（G）≥5的平面图G的邻点可区别全色数。在第4章,我们研究了最大平均度小于3的图的邻点可区别边染色问题。确定了g（G）≥10和Δ（G）≥5的平面图G的邻点可区别边色数。在第5章,我们研究了K₄-minor-free图的邻点可区别边染色问题。证明了:若G是一个Δ（G）≥5的不含孤立边的K₄-minor-free图,则Δ（G）≤χ′_α（G）≤Δ（G）+1;且χ′_α（G）=Δ（G）+1当且仅当G含有两个相邻的最大度点。

全文目录

摘要  3-4
ABSTRACT  4-6
目录  6-8
1 绪论  8-15
  1.1 基本概念  8-9
  1.2 图的邻点可区别边染色和全染色问题的研究现状  9-14
  1.3 本论文的主要结果  14-15
2 外平面图的邻点可区别全染色  15-26
  2.1 外平面图的结构性质  15-17
  2.2 最大度为3的外平面图  17-21
  2.3 最大度至少为4的外平面图  21-26
3 低最大平均度的图的邻点可区别全染色  26-36
  3.1 最大平均度小于3的图  26-31
  3.2 最大平均度小于8/3的图  31-36
4 低最大平均度的图的邻点可区别边染色  36-50
  4.1 最大平均度小于5/2的图  36-41
  4.2 最大平均度小于3的图  41-44
  4.3 最大平均度小于7/3的图  44-50
5 K_4-minor-free图的邻点可区别边染色  50-57
  5.1 一个结构引理  50-51
  5.2 邻点可区别边色数的刻画  51-57
参考文献  57-60
在学期间的研究成果及发表的论文  60-61
致谢  61-63

图的邻点可区别全染色和边染色

内容摘要

全文目录

相似论文