本文中不加特殊说明，所有图都是有限简单图.分别用V(G)，E(G)，△(G)和δ(G)来表示图的点集，边集，最大度和最小度.本文主要研究与四色猜想和图的非正则强度有关的图染色问题，主要包括:局部非正则边染色，列表1-2-3猜想，邻和可区别边染色，反魔幻标号猜想，图的DP-染色.　　一个图被称为是局部非正则的，如果图中任意两个相邻顶点的度都不相同.图的局部非正则k-边染色是指用集合{1，2,…，k}中的元素给边染色使得图中同种颜色导出的子图都是局部非正则的.但并不是所有的图都存在局部非正则边染色.如果G存在一个局部非正则边染色，那么称图G是可分解的.在2015年，Baudon，Bensmail，Przyby(l)o和Wo(z)niak猜想每个可分解的图都存在局部非正则3-边染色.近来，Bensmail等人证明了第一个一般图的局部非正则边色数的上界，为328.后来Borut等人又将这个界改进到了220.本文中，将通过证明任意的可分解的二部图都存在局部非正则5-边染色来推广一般图的结论，得到一般可分解图的上界是184.　　如果一个图中不含孤立边，那么称这个图为常规图.图G的k-边赋权φ是指函数φ:E(G)→{1，2，…，k}.称k-边赋权是正常的如果有∑e(∈)uφ(e)≠∑e(∈)vφ(e)对任意的边uv∈E(G)都成立.2004年，Karo(n)ski,Luczak和Thomason提出了著名的1-2-3猜想:任意的常规图G都存在一个正常的3-边赋权.这个猜想得到了广大学者的关注，目前最好的结果是k=5.称图G是（k，k）-可选的，如果对任意的列表分配L，其中每个顶点v∈V(G)的列表L（v）含有k个实数，每条边e∈E(G)的列表L(e)含有k个实数，G都存在一个全赋权Φ:V(G)∪E(G)→R使得φ(z)∈L(z)对每个z∈V(G)∪E(G)都成立，并且任意两个相邻的顶点都含有不同的点和，这里顶点v∈V(G)的点和是指v的权值与点v关联的边上的权值的和.在2011年，Wong和Zhu猜想每个常规图是(1，3)-可选的.显然，这个猜想是1-2-3猜想的列表形式.一些特殊图比如完全图，完全二部图，树，一些特殊图的笛卡尔积，以及最大平均度小于11/4的常规图都是(1，3)-可选的.在2015年，Wang和Yan证明了任意的常规图G是（1，[4△(G)+8/3]）-可选的.运用组合方法证明了任意常规图G是(1，△(G)+2)-可选的.　　一个图的正常边染色是指用集合{1，2,…，k}中的元素给图中的每条边染色使得任意相邻两条边染不同的颜色.如果在1-2-3猜想的基础上加上“正常边染色”的限制，那么这种染色就变成了邻和可区别k-边染色，或者简写为NSD-k-边染色.在2013年，Flandrin等人研究了树，圈，完全图，完全二部图的邻和可区别边染色.基于这些结果，他们猜想如果G是一个至少含有3个顶点且G≠G5的连通图，那么x∑(G)≤△(G)+2.Flandrin等人还证明了对于最大度△(G)≥2的连通图G有x∑(G)≤[7△(G)-4/2]成立.Wang和Yan将这个界改进到了[10△(G)+2/3].后来，Przybylo证明了ch∑(G)≤2△(G)+col(G)-1，其中col(G)是图G的染色数.最近，Przyby(l)o和Wong证明了ch∑(G)≤△(G)+3col(G)-4.给出了一般图的上界ch∑(G)≤△(G)+[5col(G)+1/2]，这个界覆盖了之前的结果.Dong等人研究了稀疏图的NSD-k-边染色.更具体地，他们证明了下面的结果:设G是一个常规图.如果△(G)≥5且mad(G)＜5/2，那么x∑(G)≤△(G)+1，其中mad(G)=max{2|E(H)|/|V(H)||H(∈)G}.后来，GaG等人将这个界从5/2改进到8/3.将8/3提高到3-2/△(G).同时，还证明了如果G是最大度△(G)≥5且mad(G)＜3的常规图，那么x∑(G)≤△(G)+2.另外，证明了如果△(G)=3且mad(G)＜5/2，那么x∑(G)≤5.　　含有m条边的图G的一个k-标号是指从E(G)到含有m+k个正实数的集合S的单射.顶点v∈V(G)的点和是指与v关联的所有边上的颜色的加和.如果在图G的一个k-标号中，任意两个顶点的点和都不相同，那么称这样的k-标号为点可区别标号.一个k-标号是反魔幻标号如果它是一个点可区别标号并且标号集合是S={1，2，…，m}.如果一个图存在反魔幻标号，那么称这个图是反魔幻的.如果在一个k-标号中任意两个相邻的顶点的点和不同，那么这个k-标号是局部k-反魔幻标号.称一个图是局部反魔幻的，如果它存在一个局部反魔幻标号.在1990年，Hartsfield和Ringel猜想每个常规的连通图都是反魔幻的.本文将研究与这一猜想相关的两个问题.　　对任意一个简单图G，给图中所有的边一个方向使得图G变成一个有向图→G，称→G为图G的定向.如果图G存在一个定向→G，并且→G存在一个标号使得→G中任意顶点的出边上的标号和减去入边上的标号和不同，其中标号集合S={1，2,…，m}，那么称→G是图G的反魔幻定向.2010年，Hefetz，Mütze和Schwartz引入了这一概念，并且在同一篇文章中提到了下列问题:每个连通图都存在一个反魔幻定向.同时他们证明了几乎所有正则图都存在反魔幻定向.注意到如果一个二部图是反魔幻的，给每条边一个从一部分顶点到另一部分顶点的方向，那么这就是一个反魔幻定向.因此正则二部图存在一个反魔幻定向.一个二部图是双正则的如果每部分顶点都有相同的度.证明了任意的双正则二部图存在一个反魔幻定向.　　作者Arumugam等人以及Bensmail等人在不同的文献中分别猜想每个常规连通图G用集合S={1，2，…，|E(G)|}中的元素标号的话都存在一个局部反魔幻标号.Bensmail等人证明了当标号集合是S={1，2,…，|E(G)|+6}时，最大度是3的图存在一个局部6-反魔幻标号.直接证明了最大度是3的图是局部反魔幻的.在他们的同一篇文章中，还证明了当标号集合是S={1，2，…，|E(G)|+4}时，每个常规的2-退化图存在一个局部4-反魔幻标号;如果标号集合是S={1，2，…，|E(G)|+k}的话，每个常规图存在一个局部k-反魔幻标号，其中k=min{2△(G)，|E(G)|}证明了两个关于一般图的结论.设G是一个常规图，最大度是△(G).如果G中的所有顶点的度都是奇数，那么G是局部(△(G)+1)-反魔幻的;否则的话，G是局部△(G)-反魔幻的.还证明了G是局部[3col(G)/2+3]-反魔幻的.　　在解决平面图的列表点染色问题时，Dvo(r)ák和Postle介绍了一个新的概念:DP-染色（他们称之为对应的染色）.图G的DP-染色把从列表L中找一个正常点染色问题归结为在一个辅助图H(G，L)中寻找一个比较“大”的独立集的问题，其中辅助图H(G，L)的点集是{（v，c）∶v∈V(G)且c∈L(v)}，边集包含两部分:　　·对于任意的顶点v∈V(G)，(v，c)与(v，c)相邻，其中c，c∈L(v);　　·对于任意的边uv∈E(G)，(u，L(u))与(v，L(v))之间的边是一个任意的匹配（可能为空).　　这个思想来源于Plesnevi(c)和Vizing把正常k-染色问题归结为在笛卡尔积G□Kk中寻找大小为|V(G)|的独立集的问题.如果对于任意的列表L，其中对任意顶点v∈V(G)，有|L（v）|≥k，H中都存在一个大小为|V(G)|的独立集，那么称图G是DP-k-可染的.称最小的k为图G的DP-染色数，记作xDP(G).显然xDP(G)≥xe(G)对任意的图都成立，但是它们之间相差甚远.在第四章中介绍了简单图的DP-染色，并且证明不含4-圈和3-圈相邻的可平面图的DP染色数是4.