图论是数学中重要独立的分支之一.近三十年,图论正经历着蓬勃发展的时期,表现出年轻学科所具有的强大的生命力.自四色问题被提出来之后,它一直引领着图论中染色理论的发展,涌现出了丰富的理论成果.从而图论的染色问题一直是图论研究的焦点问题.图论的染色理论在许多学科中都有广泛的实际应用,如物理学,生物学,运筹学,计算机科学,社会科学等.另外,图的染色理论在离散数学领域有着非常重要的地位,其中许多貌似无关的问题都可由转化为图染色问题.因此,T.R.Jensen和B.Toft断言,图染色理论在离散数学中处于中心地位.经典的染色问题包括图的点染色,边染色,面染色,全染色等,并且都得到深入的研究.后来数学家们在这些染色的基础问题上添加各种不同的限制,拓展出了新的染色领域.2006年,赖宏建等人在《离散数学》上首次提出了条件染色的概念并得到了一些结论,在《图的条件染色》一文中,他们给出了一般图的条件色数上界,一些特殊图的条件染色,以及正常图的几个充分条件等.2012年,孙磊,刘婷提出了非正常条件染色的概念,在刘婷的毕业论文中,她研究了几类特殊图的非正常条件色数.在本文中将继续研究图的条件染色和非正常条件染色问题.本文第一章主要介绍了文章中涉及的一些基本概念和符号,阐述了图的染色问题的历史及发展.本文中未加说明的符号及定义参见文献[1].定义1若k为正整数,令k={1,2,…,k},图G的一个正常k-染色是一个映射c：V(G)→k使得相邻点获得的颜色不同.使G有一个正常染色的最小k值称为G的色数,记为)x(G).定义2对于正整数k和r,图G的一个正常(k,r)-染色是满足以下条件的一个映射c：V(G)→k,(1)若uu∈E(G),则c(u)≠c(u)；(2)对(?)∈V(G),|c(NG(u))|≥min{|NG(u)|,r).对固定的r,使得G有一个正常(k,r)-染色的最小正整数k称为G的条件色数,记为xr(G).图的条件染色是在正常染色的基础上对任一点的邻点的颜色种类添加限制,使得任一点邻点的颜色种类不小于邻点个数和r的最小值.由条件色数的定义显然得到X1(G)=X(G).定义3[7]称一个图G是正常的,若X2(G)=X(G)类似的,称一个图G是r-正常的,若Xr(G)=X(G).在第二章中,主要研究了图的条件染色,给出了r-正常图的两个充分条件并讨论了几类特殊图的3-条件色数和几类特殊图的r-条件色数.定理2.1.12设G为简单图,α(G)=α,△(G)≤[n-rα/α-1]-1,则G是r-正常的.定理2.1.13对于n阶图G,若除去一对相邻点的度和不作要求外,其余各相邻点的度和大于n,则G为正常的.定理2.1.14设G为n个顶点的连通图,若除一组度和不考虑外,任意其导出子图连通的r个顶点,其度和大于礼(r-1),则G是r-正常的.定理2.2.2若G为外平面图,且δ(G)=2,则)x3(G)≤6.定义4如果平面图G的最大度△(G)=|V(G)|-k,k=1,2…,则称G为一个hk-图,k=1,2的hk-图称为高度平面图.根据高度平面图的定义,给出了一些具有限制条件的高度平面图的3-条件色数的上界.定理2.2.8设是G是一个|V(G)|≥2的h1-图,则x3(G)≤6.定理2.2.9设G是|V(G)|≥9的h2-图,且G含有两个相邻的最大度点w1,w2,那么x3(G)≤5.定义5[32]若G为简单图,V(G)={v1,v2,…,vn],把m个G的顶点vju∈G(j0∈{1,2,…,n))连成圈,所得到的新图记为Cm·G(vjo),简记为G*,其中Gi(i=1,2,…,m)为G的m个复制图.即新图的点集和边集为：定义6图G的一个非正常(k,d)*-染色是一个映射c：V(G)→k,使得：对(?)v∈V(G),在v的邻点中最多存在d个与v染相同的颜色.使G有一个非正常的(k,d)*-染色的最小k值称为图G的非正常色数.设v是图G中一点,且w为v的邻点,对于染色c,若存在c(v)=c(w),则称点w为坏点.非正常染色是在正常染色的基础上对点的邻点的染色规则进行放松,每个点的邻点集中允许出现d个坏点.由非正常色数的定义显然得到图G一个非正常(k,0)*-染色即是图G一个正常的k-染色.定义7对整数k>0,r>0,s≥0,图G的一个(r,s)-非正常条件染色是一个映射c：V(G)→k,使得：(1)对(?)v∈V(G),最多存在s个顶点v1,v2,…,vs∈N(v),满足c(v1)=c(v2)=…=c(vs)=c(v);(2)对(?)u∈V(G),|c(N(v))|≥min{|N(v)|,r).使G有一个(r,s)-非正常条件染色的最小k值称为图G的非正常条件色数,记为X(r,s)(G).图的非正常条件染色是在正常染色的基础上一方面对任一点的邻点的颜色种类添加限制,使得任一点邻点的颜色种类不小于邻点个数和r的最小值,一方面对任一点的邻点的染色规则进行放松,使得任一点的邻点中的坏点个数至多为s.由非正常条件色数的定义显然得到图G一个用k种颜色染的(1,s)-非正常条件染色即为图G非正常(k,s)*-染色,图G一个(r,0)-非正常条件染色即为图G一个条件染色,图G一个(1,0)-非正常条件染色即为图G一个正常点染色.本文的第三章主要研究了图的非正常条件染色,给出了图的(r,s)-非正常条件色数的一个上界,并讨论了特殊图的(r,s)-非正常条件色数.定理3.1.15对于连通图G,T为G的一颗支撑树,G0=G\E(T),则X(r,s)(G)≤X(r,s)(T)+X(r,s)(G0),其中r≥2,s≥1.定理3.1.16对于图G,X(r,s)(G)≤△2-△,其中r≥2,s≥1.定义8设G是一简单图,V(G)=(v1,v2,…,vn),I2是两个点的独立集,G是用I2代替G的每个顶点所得到的图.I2中每个点仍按对应点的连边方式与其他点连边.G[I2]的点集和边集如下:V(G[I2])={v1,v2,…,vn,v’1,v’2,…,v’n), E(G[I2])=E(G)u{v’iv’j,v’ivj|vivj∈E(G)}.G[I2]称为G的点分裂图.定理3.2.2若n,s≥1的整数,I2为两个点的独立集,则