简单图无圈着色.pdf

重庆大学硕士学位论文中文摘要

摘要

图的着色问题是由地图的着色提出的,它是最著名的 NP-完全问题之一。图的
着色理论不仅在离散数学和组合分析等数学理论中有着广泛的应用,近年来,随
着生产管理、交通运输、军事、计算机和通讯网络等方面许多离散型问题的出现
与研究,图论的着色问题具体应用在解决安排会议或考试的日程以避免冲突和安
排化学品的存储上以避免相互反应等问题上并取得了较好的效果。
图的无圈着色和线性着色是在顶点着色的基础上提出的。本文研究了几类简
单图的无圈着色以及与之密切相关的线性着色问题,主要分为三部分:
在第一部分中(见论文第一、二章)对图论着色问题的研究历史、背景、基
本概念等进行一个综述。主要包括:正常顶点着色、无圈着色、星着色、3-不足着
色和线性着色等,为后文的论证打好基础。
第二部分(论文第三、四章)探讨图的无圈着色和线性着色问题。
无圈着色在研究星着色、2-距离着色等问题中具有重要意义,这类着色问题通
常会以无圈色数作为下界来逼近其色数的确界,因此在着色研究中只要无圈着色
有进展,其他一系列着色就会有相应的改进。第三章通过分析图的结构,运用归
纳等数学理论方法给出了最大度为 5 的非正则图和高度图的无圈色数界,并通过
群论中置换思想给出含有割边或割点的五正则图无圈色数的更加精确的上界。第
四章首先运用 J. Heuvel 的一个引理缩小了最大度大于 11 的平面图的线性可选择
着色色数的上界;然后通过分析最大度为 4 的图的着色特点得到了这一类图线性
色数的较为精确的上界,并给出具体算法说明这个界是可达的;随后证明了 d 维
网格线性着色的确界。
最后是对本文结论、主要创新之处的总结,以及有关无圈着色和线性着色研
究的展望。

关键词:无圈着色;线性着色;线性可选择着色;d 维网格




I
重庆大学硕士学位论文英文摘要

ABSTRACT

The graph coloring problem is extended from the map coloring, it is one of the
most famous plete problem. The graph coloring theory is used in the
mathematical theory, such as mathematical theory and discrete mathematics. With the
development of transport work, the graph coloring problem has
more and more applications. It can be used to solve specific problems, such as arrange
meetings or schedule, chemical storage, and has obtained a very good effect.
The acyclic coloring and linear coloring is a generalization of the graph coloring
theory. The main research object of the paper is acyclic coloring of several simple
graphs. The linear coloring of graphs are also concerned. This paper includes three parts
as follows.
The first (Chapter 1 and 2 are included) introduces the historical background and
fundamental conception of coloring theory. It includes the proper vertex coloring,
acyclic coloring, 3-frugal coloring and linear coloring.
The second part (Chapter 3 and 4 are included) is the main text. It expores the
acyclic and linear coloring.
The acyclic coloring is very important for the resear