关于图着色的若干参数的研究-应用数学专业论文.docxVIP

重庆大学硕士学位论文中文摘要 重庆大学硕士学位论文 中文摘要 I I 摘 要 本学位论文主要考虑图的着色问题。图的着色理论是图论研究的重要内容之 一，并且在离散数学，组合数学和现实生活中都有着重要的应用。随着科技的发 展和现实生活的需要，各种各样的着色问题已被国内外的学者广泛推广和研究， 诸如全着色、无圈着色、强边着色、星着色、强着色、r-强边着色等。由于确定一 个图的点色数或边色数是 NP—完全问题，因此，确定图的这些特殊着色数同样是 NP—完全的。目前对这些问题的讨论基本上是在对一些图做了一定的条件限制， 从而对其进行的研究。 本论文共分五章，我们主要研究了一类图的 r-强边着色，完全立方 Halin 图的 2-距离着色、完全立方 Halin 图的星着色和 Halin 图的星着色等。其中，在第一章 我们首先对图论的发展及其应用做了简要的介绍，并且还给出了本论文常用的一 些符号表示。 在第二章，我们主要介绍了本论文所研究内容的研究背景、研究历史和研究 综述，最后还给出了本文所研究的内容；在第三章，我们主要研究了一类图的 r- 强边着色，并得到某一类图的 1-强边着色和不含孤立边的图的 2-强边着色的色数 界；在第四章，我们主要研究了完全立方 Halin 图的 2-距离着色、星着色和 Halin 图的星着色，并且得到完全立方 Halin 图 2-距离着色和 Halin 图星着色较优的色数 界，完全立方 Halin 图完美的星色数 4；在第五章，我们总结了本文的主要研究成 果。 关键词：Halin 图，完全立方 Halin 图，星着色，2-距离着色，r-强边着色 重庆大学硕士学位论文英文摘要 重庆大学硕士学位论文 英文摘要 II II ABSTRACT This dissertation is devoted to study the graph coloring problems. The coloring of graphs is one of the significant branches in graph theory. And in the discrete mathematics and combinatorial mathematics, the coloring problem has a wide range of applications. With the development of technology and their wide applications in reality, some new coloring concepts, such as total coloring, cycle coloring, strong edge coloring, star coloring, strong coloring , r-strong edge coloring and so on, have come forth in the latest decades. Since it is NP-complete to determine the vertex chromatic number and edge chromatic number of a general graph, it is also NP-complete to determine these generalized chromatic numbers. Thus, researchers mainly focus on some special classes of graphs and their various coloring problems． This dissertation consists of five chapters. Star coloring and 2-distance coloring of complete cubic Halin graphs, star coloring of Halin graphs, and r-strong edge coloring of a kind of graphs are investigated in this dissertation. In Chapter 1, we firstly introduced the development and application of the Graph theory, and gave some definitions and notations used throughout this dissertation. In Chapter 2, we gave a chief survey on graph col