图的染色理论在离散数学的研究领域中处于中心地位。它还经常出现在看上去没有或者仅有一点联系的研究领域中。图的染色理论非常有用。时间表的编制,排序问题,调度问题,以及由它们演化而来的其他问题等等,都可以用染色理论来处理。图G=(V(G),E(G))。对一个正整数k,图G的一个正常k染色是指一个满射c:V(G)→{1,2…,k),满足如下条件:如果点u和点v在G中相邻的话,那么c(u)≠c(u),即u和v要染不同的颜色。按照上述方法染色,所需要用到的最少颜色数被我们称为图的色数,记为X(G)。对图G的一个顶点子集S,我们用c(S)来表示在c这种染色方式下S中所用的不同颜色的集合。到目前为止,图的染色有很多推广,包括图的边染色,列表染色,地图染色和全染色等等。我们这里研究的是图的条件染色。对于给定的正整数k和r,图G的一个正常的(k,r)-条件染色是指满足如下两个条件的满射c:V(G)→{1,2,…,k}:(C1)如果u和v在图中相邻,那么它们必须染不同的颜色；(C2)图的任一顶点v的邻域所染的不同颜色数必须大于等于min{d(v),r}。对于给定正整数r,使得图G具有一个正常(k,r)-条件染色所需的最少的颜色数称为图G的第r阶条件色数,记为Xr(G)。由Xr(G)的定义可知X(G)=X1(G),因此条件染色是传统染色的一个自然推广。但是条件染色又跟传统染色有很多的不同。在2006年的一篇文章中,赖虹建等人给出了许多条件染色的性质和定理说明了它在图论性质方面的很多不同。在本文中,我们将主要讨论条件染色问题在算法方面的表现。　　 本研究分为总价格部分：第一部分讨论了一般图的条件染色的算法表现,第二部分集中考察了在无爪图中的(3,2)-条件染色的性质和算法。第三部分给出了一些其他的关于条件色数的结果。第一部分包括第二章和第三章。在第二章中,我们首先考察了一般图的条件染色的算法复杂性问题。我们主要证明了判定对于给定任意大的围长,最大度不超过3的平面二部图是否可以(3,2)-条件染色这个问题是NP-完备的。这个结果跟传统的染色有很大的不同。在传统的染色中,对于最大度不超过3的图的染色问题有多项式时间算法来解决。我们也证明了在传统染色中的一些著名ⅣP-完备问题在条件染色中也是同样成立的。在第三章中,我们将会说明(3,2)-条件染色问题对于给定树宽的图是有多项式时间算法的。我们也会对最大度大于等于4的一般图给出一个(△+1,2)-条件染色的多项式时间算法。第二部分是第四章。在这一章中,我们将集中讨论无爪图的第2阶条件3染色问题。首先,我们证明了判断一个最大度为3的无爪图是否(3,2)-条件可染问题是NP-完备的。其次,在屏蔽一类子图后,我们在最大度为3的无爪图类中找到了一类非平凡图类对于前述问题是有线性时间算法的。最后,我们给出三个线性时间算法:第一个算法是用来识别这类非平凡图的；第二个算法是用来判定这个图是否是(3,2)-条件可染的；第三个算法是对这个(3,2)-条件可染的图给出一个具体的最优染色方案。第三部分是第五章,列出了我们得到的一些其他的关于条件色数的性质和结果。