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

若干图类的Smarandachely邻点全染色

作　者: 文飞
导　师: 李沐春
学　校: 兰州交通大学
专　业: 运筹学与控制论
关键词: 图全染色 Smarandachely邻点全染色 Smarandachely邻点全色数
分类号: O157.5
类　型: 硕士论文
年　份: 2011年
下　载: 20次
引　用: 0次
阅　读: 论文下载

内容摘要

对于简单图G,f是图G的一个正常全染色(即：相邻顶点、相邻边以及关联元素都染不同色的一个全染色).进一步,如果相邻两点的色集合互不包含,则称该染色法f为Smarandachely邻点全染色,把所用最少颜色数称为该图G的Smarandachely邻点全染色数.其中某一点的色集合为点及其关联边所染的颜色构成的集合.近年来,穷举法、组合分析法以及结构拼凑法成为了研究图染色的主要方法.所谓穷举法就是在已知图的某种染色的色数的下界(上界)之后,在这个图的同构类里找出一个图施行这种染色,通过给每个元素染色来说明其色数是存在的；组合分析法就是通过分析图的结构,运用组合学的来研究图染色的方法；结构拼凑法是从图的结构出发,对图的局部进行着色,然后通过拼凑来实现整个图的染色.本文应用上述三种方法,研究了路、圈、星、扇、轮、完全图、联图、四种积图(直积图、卡氏积图、强积图、半强积图)和若干3-正则图的Smarandachely邻点全染色,并得到了这些图类的Smarandachely邻点全色数.文章分为以下四部分：第一章介绍了图的一些基本概念及其猜想.第二章给出了若干简单图以及联图的Smarandachely邻点全染色结果.第三章主要研究了四种积图(直积图、卡氏积图、强积图、半强积图)的Smarandachely邻点全染色,得到了其Smarandachely邻点全染色,进一步验证了这些图对Smarandachely邻点全染色猜想成立.第四章构造了若干类3-正则图,并给出了若干3-正则图的Smarandachely邻点全染色,得到了其色数,进一步验证了3-正则图的Smarandachely邻点全染色猜想成立.

全文目录

摘要  4-5
Abstract  5-8
引言  8-10
1 基本概念及相关猜想  10-13
2 若干简单图及联图的Smarandachely邻点全染色  13-17
  2.1 一些简单图的Smarandachely邻点全染色  13-15
  2.2 一些联图的Smarandachely邻点全染色  15-17
3 四种积图的Smarandachely邻点全染色  17-46
  3.1 四种积图的定义  17-18
  3.2 若干直积图的Smarandachely邻点全染色  18-23
  3.3 若干笛卡尔积图的Smarandachely邻点全染色  23-32
  3.4 若干强积图的Smarandachely邻点全染色  32-40
  3.5 若干半强积图的Smarandachely邻点全染色  40-46
4 若干3-正则图的Smarandachely邻点全色数  46-65
  4.1 三类3-正则Halin图的Smarandachely邻点全染色  47-51
  4.2 两类3-正则图的Smarandachely邻点全染色  51-55
  4.3 一类3-正则重圈图的Smarandachely邻点全染色  55-65
结论  65-66
致谢  66-67
参考文献  67-69
攻读学位期间的研究成果  69

若干图类的Smarandachely邻点全染色

内容摘要

全文目录

相似论文