图论是离散数学的骨干分支,它不仅具有重要的理论意义,而且具有重要的实际意义,它在管理科学、计算机科学与技术、通信工程等领域都有广泛的应用。图论的研究始于200多年前,Eulcr用图论的方法解决了格尼斯堡七桥问题。自二十世纪五十年代以来,由于计算机科学的迅速发展,有力地推动了图论的发展,关于图论方面的结果大量涌现。四色猜想作为图的染色问题的起源,一直引领着图论的发展,并使得图的染色理论成为图论中的一个重要分支。本文主要讨论图的几类染色问题,包括图的均匀染色和均匀可选择性、列表染色及邻和可区别的边染色等。本文所研究的图均为简单图,文中我们用V(G),E(G),δ(G)和△(G)分别表示图G的点集、边集、最小度、最大度。对于任意的v∈V(G),符号dG(v)表示图G中与点v相关联的边的条数,称为点v在图G中的度,简记为d(v)。令S是一个集合,符号|S|表示集合S中所含元素的个数。对于任意的实数x,符号[x]和LxJ分别表示不小于x的最小整数和不大于x的最大的整数。符号ad(G)表示图G中所有点的度数的平均值,即ad(G)=Σv∈V(G)d(v)/|V(G)|,称为图G的平均度。符号mad(G)表示图G的所有子图的平均度的最大值,称为图G的最大平均度。如果图G的所有点的度数都为k,则称图G为k-正则图。如果图G的任何子图都含有一个度数不超过d的点,则称图G为d-退化图。长度为k的圈称为k-圈。长度为3的圈又称三角形。令C为图G的一个k-圈,如果存在边xy∈E(G)一E(C),则称圈C为带弦的k-圈。我们称图G中所含的最小的圈的长度为图G的围长,记为g(G)。如果我们能将一个图G画在一个平面上,使得图G的任何两条边仅在顶点处相交,则称图G是可平面的,并称图G的这种画法为它的平面嵌入。方便起见,我们称一个可平面图的平面嵌入为平面图。一个平面图G将一个平面分割成很多小的区域,称每一个小的区域为图G的面。符号F(G)表示图G的所有面的集合。下面我们简单介绍一下本文所研究的几类染色的概念。图G的均匀染色是一种特殊的点染色。如果图G的点集V(G)可以划分成k个独立的子集V1,V2,…,Vk,使得||Vi|-|Vi||≤1(1≤i,j≤k),则称图G是均匀k-可染的。使图G能够均匀k-可染的最小正整数k,称为图G的均匀染色数,记为Xe(G)。如果χe(G)=k,且对于任意的l>k,图G是均匀l-可染的,则我们称k为图G的均匀染色数的界,记为Xe*(G)。对图G的每个点v∈V(G)给定一个相应的颜色集合记为L(v),如果存在图G的一个正常点染色c,使得对于任意的点v,都有c(v)∈L(v),则称图G是列表L-可染的。给定一个颜色列表L,如果对于任意的点v,都有｜L(v)｜=k,则称L为k-一致列表。如果对于任意k-一致列表L,图G是列表L-可染的,并且每种颜色所含的点数不超过[|V(G)|/k],则称图G是均匀k-可选择的。图G的列表边和列表全染色是边染色和全染色的一种推广。对图G的每个元素x∈E(G)∪V(G)给定一个相应的颜色集合记为L(x),称L={L(x)|x∈E(G)∪V(G)}为图G的一个全列表。若图G存在正常全染色c使得对于任意的元素x∈E(G)∪V(G),都有c(x)∈L(x),则称G是列表全L-可染的。给定一个颜色列表L,如果对于任意的元素x∈E(G)∪V(G),都有｜L(x)|=k,则称图G是全k-可选择的。使图G存在全k-可选择的最小正整数k称为G的列表全色数,记为X"l(G)。列表边色数的定义类似与列表全色数的定义,所不同的是仅考虑对图G的边进行染色,这里不再重述。图G的邻和可区别的边染色是一种特殊的边染色。图G的正常[k]-边染色,是利用颜色集[k]={1,2,…,k}的图G的一个正常边染色。如果一个正常边染色使得对于图G的任意一条边vv∈E(G),都有与点u关联的边上的颜色数之和不等于与点v关联的边上的颜色数之和,则称它为邻点可区别的[k]-边染色。符号ndi∑(G)表示使图G具有邻和可区别的[k]-边染色的最小颜色数k。本文主要讨论图的均匀染色,均匀可选择性,列表边染色,列表全染色,邻点可区别的边染色,分四章进行讨论。第一章,我们首先介绍了一些图论中的概念,术语和定义；然后,给出了本文所要讨论的几类染色的提出及研究进展；最后,我们给出了本文所要介绍的主要结论。第二章,我们讨论了图的均匀染色和均匀可选择性。我们研究了平面图,改进了Bu等人在文章[20,57,68,85,91,92]中的关于平面图的结果,得到了一系列更好的结果；我们还研究了具有最大平均度限制的一般图的均匀染色和均匀可选择性。第三章,我们讨论了图的列表边染色和列表全染色。对于某些特殊平面图,验证了列表边染色猜想和列表全染色猜想。第四章,我们讨论了图的邻和可区别的边染色。我们研究了平面图和具有最大平均度限制的一般图,给出了平面图的邻和可区别的边染色数的一个上界；此外,对于具有小的最大平均度限制的图,我们推广了Wang等人在文章[72]中的结果,从而进一步验证了邻和可区别的边染色猜想。