图论作为数学和信息科学的一门交叉学科,它以图为研究对象,将现实问题抽象成图,广泛的应用在各个领域,如矩阵运算、任务调度、网络通信、物品储藏、频率分配等。图染色作为图论研究领域的重要方向之一,同样是将生活中的实际问题抽象成图论模型,然后按照一定的规则进行分类,利用图染色的方法解决。目前,大量的学者们已对图染色问题作了许多的探讨和研究,寻找到了求解各类染色问题的具体方法,主要有基于搜索解空间的染色算法和基于目标函数的染色算法。基于搜索解空间的染色算法一般解决简单的点染色、边染色、全染色;基于目标函数的染色算法解决约束条件较多的邻点和可区别染色、点可区别染色、强边染色、点可约染色等。这两类图染色算法只针对一些特殊图染色或者特殊图集(Wn、Kn、Kn,n、C3（n）、mCn、D（G）、Sn+Fn、Wn+Fn、Mn（Cp）)进行处理得到染色结果。但随着染色条件增加,传统的染色算法将解决不了新出现的染色情况,故需要寻求新的染色算法来解决。因此,本文针对随机图的点和可约边染色、点和可约全染色、邻点和可约边染色3个问题进行研究,提出了解决这三类问题地具体方案,并设计了相关的点和可约染色算法。本文的主要研究工作如下:（1）介绍图染色的相关概念、（邻）点可约边（全）染色、（邻）点和可约边（全）染色的研究现状,以及点和可约染色研究与传统图染色研究方法的区别。（2）设计并完成了基于逐步寻优的点和可约边染色算法。首先,该算法依据点和可约边染色定义和逐步寻优的思想来确定的。其次执行算法得到10个点以内12205208个所有非同构图、19个点以内522957个树图的非同构图、15个点以内的所有单圈图和双圈图的点和可约边染色矩阵和最大染色数,并统计结果进行分析得到若干图的点和可约边染色结论和猜测。除此之外,为了优化点和可约边染色算法,设计了另外两种点和可约边染色算法,分别为基于规则集的点和可约边染色算法和基于方程式的点和可约边染色算法。并通过对这三种点和可约边染色算法的测试和结果集的对比,得到基于逐步寻优的点和可约边染色算法在性能和复杂度上都优于其他两种点和可约边染色算法。（3）设计并实现了点和可约全染色算法和邻点和可约边染色算法。并利用这两种算法对图数据集进行处理,从而得到10个点以内12205208个随机图、12个点以内特殊图的两类点和可约染色情况。最后,通过结果集分析,给出了若干联图和特殊图的定理证明。