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

关于几类图的分数色数

作　者: 王彩虹
导　师: 刘西奎
学　校: 山东科技大学
专　业: 应用数学
关键词: 分数着色分数色数积运算和运算正规积运算超图概率方法
分类号: O157.5
类　型: 硕士论文
年　份: 2008年
下　载: 6次
引　用: 0次
阅　读: 论文下载

内容摘要

分数着色是顶点着色的一个推广,对于某些具体问题,它能更好地刻画解决。分数色数作为图的重要参数之一,是非常具有研究价值的。文中首先给出图的分数色数的定义,研究了简单图的和运算、正规积运算及联运算的分数色数,并且根据顶点可迁图的分数色数研究循环图、圈的幂的分数色数及其积运算的分数色数。从而得到各个运算的一个比较严格的上界,进而完善图的运算的分数色数与其因子的分数色数之间的关系,得到求图的和运算、正规积运算、联运算的分数色数的比较精确的计算方法。然后将分数着色推广到有限超图中,研究其在有限超图中的性质。文中主要研究了超图的奇偶圈、线性超图及其相关的对偶超图、2-分图、线图、关联图、H_q~p(r)超图、r-一致循环超图等特殊超图的分数色数;并确定了无环超图的积运算的色数与因子的分数色数之间的关系及超图的字典积运算的分数色数与因子的分数色数间的关系。最后用概率方法证明了分数色数的一个上界的成立,同时得到一个构造图的分数着色的算法。

全文目录

摘要  5-6
ABSTRACT  6-9
1 绪论  9-19
  1.1 问题的提出  9-13
  1.2 国内外研究现状  13-14
  1.3 基本符号和术语  14-18
  1.4 论文的主要研究内容与安排  18-19
2 图的几种运算的分数色数  19-27
  2.1 基本概念与预备引理  19-22
  2.2 主要结果及其证明  22-24
  2.3 一类顶点可迁图的积运算的分数色数及其证明  24-27
3 超图的分数色数  27-36
  3.1 基本概念与预备引理  27-28
  3.2 主要结果及其证明  28-36
4 概率方法在分数色数中的应用  36-41
5 结束语  41-42
致谢  42-43
参考文献  43-46
攻读硕士期间的研究成果  46

关于几类图的分数色数

内容摘要

全文目录

相似论文