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

关于图着色的若干参数的研究

作　者: 赵灿鸟
导　师: 谢德政
学　校: 重庆大学
专　业: 应用数学
关键词: Halin图完全立方Halin图星着色 2-距离着色 r-强边着色
分类号: O157.5
类　型: 硕士论文
年　份: 2011年
下　载: 38次
引　用: 1次
阅　读: 论文下载

内容摘要

本学位论文主要考虑图的着色问题。图的着色理论是图论研究的重要内容之一,并且在离散数学,组合数学和现实生活中都有着重要的应用。随着科技的发展和现实生活的需要,各种各样的着色问题已被国内外的学者广泛推广和研究,诸如全着色、无圈着色、强边着色、星着色、强着色、r-强边着色等。由于确定一个图的点色数或边色数是NP—完全问题,因此,确定图的这些特殊着色数同样是NP—完全的。目前对这些问题的讨论基本上是在对一些图做了一定的条件限制,从而对其进行的研究。本论文共分五章,我们主要研究了一类图的r-强边着色,完全立方Halin图的2-距离着色、完全立方Halin图的星着色和Halin图的星着色等。其中,在第一章我们首先对图论的发展及其应用做了简要的介绍,并且还给出了本论文常用的一些符号表示。在第二章,我们主要介绍了本论文所研究内容的研究背景、研究历史和研究综述,最后还给出了本文所研究的内容;在第三章,我们主要研究了一类图的r-强边着色,并得到某一类图的1-强边着色和不含孤立边的图的2-强边着色的色数界;在第四章,我们主要研究了完全立方Halin图的2-距离着色、星着色和Halin图的星着色,并且得到完全立方Halin图2-距离着色和Halin图星着色较优的色数界,完全立方Halin图完美的星色数4;在第五章,我们总结了本文的主要研究成果。

全文目录

中文摘要  3-4
英文摘要  4-6
1 绪论  6-8
  1.1 符号说明  7-8
2 着色的基本概念与研究现状  8-14
  2.1 基本概念  8-9
  2.2 着色的基本概念和性质  9-12
    2.2.1 边着色、顶点着色的概念和性质  9-10
    2.2.2 r-强边着色和其研究现状  10-11
    2.2.3 2-距离着色和其研究现状  11
    2.2.4 星着色和其研究现状  11-12
  2.3 本文的研究内容与安排  12-13
  2.4 本章小结  13-14
3 一类图的r-强边着色  14-20
  3.1 r-强边着色的概念和研究现状  14
  3.2 一类图的r-强边着色  14-19
  3.3 本章小结  19-20
4 图的2-距离着色和星着色  20-36
  4.1 图的2-距离着色、星着色的概念与研究现状  20-21
  4.2 完全立方Halin 图的2-距离着色  21-25
  4.3 完全立方Halin 图的星着色  25-30
  4.4 Halin 图的星着色  30-35
  4.5 本章小结  35-36
5 本文的结论及展望  36-38
  5.1 本文的主要结论  36
  5.2 本文的主要创新之处  36-37
  5.3 本文的研究的展望  37-38
致谢  38-39
参考文献  39-42
附录  42

关于图着色的若干参数的研究

内容摘要

全文目录

相似论文