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

关于G_d～k图性质的研究

作　者: 蔡敏
导　师: 何文杰
学　校: 河北工业大学
专　业: 应用数学
关键词: 圈团数圈色数分数色数圈优美平面图非平面图 T－染色
分类号: O157.5
类　型: 硕士论文
年　份: 2002年
下　载: 19次
引　用: 0次
阅　读: 论文下载

内容摘要

在这篇文章当中，我们研究两种具有近互补关系的图G_d~k和C_d~k图。文章的主要部分研究G_d~k图的性质，关于C_d~k图的研究出现在讨论中。 1988年，Vince提出星色数的概念之后，得到了大量的关于星色数、圈色数的研究。引出了一类特殊的图：G_d~k图，它有点集{0，1，2，．．．．(k-1)}，当G_d~k的两点i，j满足d≤|i-j|≤k-d时，有边相连。当图的星色数用同态的观点来研究时，图G_d~k的作用与用同态的观点研究正常染色时的完全图K_n的地位是相等的。即：G是n可染色的，当且仅当G同态到K_n，对每—个有理数k/d，存在一个特殊的G_d~k图，使得G是k/d可染色的，当且仅当G同态到G_d~k。 G_~k图在研究过程中不仅具有如此重要的地位，而且G_d~k图具有很多良好的性质，在这篇文章中，我们就探讨一下图G_d~k的性质。图论中，着色问题及色数问题是十分活跃的研究课题，一些焦点问题引起了不少人们的兴趣，却有待解决，例如平面图的四色猜想，始终是悬而未决，在这篇文章中，我们将得出一个结论：G_d~k(k≥2d，gcd(k，d)=1)图除了奇圈以外，都是非平面的，并在此基础上得出有关平面图圈团数(团数)、圈色数(色数)的两个推论：任意平面图的圈团数只能是2+1/n或者不大于4的整数，如果平面图圈优美(或者优美)，那么，它满足四色定理。

全文目录

中文摘要  3-4
英文摘要  4-6
第一章绪论  6-8
第二章图论的基础知识  8-14
  §2．1 图和子图  8-10
  §2．2 平面图  10-12
  §2．3 顶点着色与色数  12-14
第三章圈染色、圈色数和分数色数  14-20
  §3．1 圈染色和圈色数引出  14-16
  §3．2 平面图的圈色数  16-18
  §3．3 分数色数  18-20
第四章 G_d~k图的引出  20-25
  §4．1 图的同态和G_d~k图  20-22
  §4．2 圈优美图  22-25
第五章 G_d~k图的一些基本性质和简单结果  25-28
  §5．1 基本性质  25
  §5．2 关于G_d~K的一些已知结果  25-28
第六章主要结果  28-35
  §6．1 图G是G_d~k（2d＜k＜3d）图的一个充分必要条件  28-31
  §6．2 图G_d~k（k≥2d，gcd（k，d）=1）的非平面性  31-35
第七章讨论  35-40
致谢  40-41
参考文献  41-43

关于G_d～k图性质的研究

内容摘要

全文目录

相似论文