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

三类特殊图的圈色数

作　者: 张媛
导　师: 毛经中；李书超
学　校: 华中师范大学
专　业: 运筹学与控制论
关键词: 圈色数色数平面图轮图 Mycielski图距离图
分类号: O157.5
类　型: 硕士论文
年　份: 2005年
下　载: 28次
引　用: 0次
阅　读: 论文下载

内容摘要

图G的星色数x~*(G)(亦称圈色数),是G的色数x(G)的一个自然推广,它最早由Vince在文献[1]中提出.对两个整数k和d,若1≤k≤d,图G的(k,d)-着色定义为映射c:V(G)→{0,1,2,…,k-1},使得当xy∈E(G)时,有d≤|c(x)-c(y)|≤k-d成立。一个图G的星色数x~*(G)=inf{k/d:G存在一个(k,d)-着色且2d≤k≤|V(G)|}。此后,朱绪鼎在文献[3]中给出了它的一个等价定义-圈色数。为统一起见,本文统一称为圈色数。本文研究了平面图、Mycielski图和距离图这三类特殊图的圈色数。本文一共分为五个部分,第一部分为引言,介绍了圈色数的定义及其等价定义,还总结了后面常会引用的定理和结论。第二、三、四部分分别总结了关于平面图、Mycielski图和距离图的圈色数的一些结论和这些问题的进展情况。其中第二部分在总结平面图的圈色数已有结论的基础上,还构造了一些新的圈色数为3或4的平面图。第五部分为展望,总结了关于这三类特殊图的圈色数的一些还未解决的问题。

全文目录

摘要  4-5
Abstract  5-7
第一章引言  7-12
第二章平面图的色数的学位论文">圈色数  12-22
  2.1 可作为平面图的圈色数的有理数r  12
  2.2 圈色数为2与3之间的有理数的平面图  12-14
  2.3 圈色数为3与4之间的有理数的平面图  14-16
  2.4 圈色数为3或4的平面图  16-22
第三章 Mycielski图的圈色数  22-30
  3.1 Xc(M(G))＜X(M(G))的图G  22-25
  3.2 Xc(M(G))=X(M(G))的图G  25-30
第四章距离图的圈色数  30-35
第五章展望  35-37
参考文献  37-40
致谢  40

三类特殊图的圈色数

内容摘要

全文目录

相似论文