图着色问题是图论中的经典问题，是组合优化问题中的一个经典NP-完全问题。该问题具有广泛的研究和应用背景，目前已经被应用于工程领域和科学计算中，例如时间调度、寄存器分配、频谱分配、网络通讯、排课安排、流媒体调度等。所有的图着色问题均可以等价于图顶点着色问题来解决，求解图顶点着色问题的算法主要有精确算法和近似算法两种类型。近似算法具有快速找解的能力，然而对于解决图着色问题，精确算法具有不可替代的作用。图顶点着色问题的目的就是对顶点进行着色。将颜色作为主要考虑因素，提出了基于极大独立集的精确算法。该算法通过求取极大独立集，将原图的着色问题转化为子图的着色问题。对随机算例的测试结果表明，该算法对顶点个数较少和密度较大的图具有较好的效果。将顶点作为主要考虑因素，提出了基于顶点选择和颜色传播的精确算法。该算法为每个顶点分配候选颜色集合，每次选择一个顶点作为决策顶点，决策顶点选择候选颜色集合中的一个颜色进行染色，并更新邻居的候选颜色集合。对标准算例的测试结果表明，该算法能够解决部分算例的着色问题，是一个整体效果较好的算法。综合考虑图的颜色和顶点，基于上述两种算法，提出了基于独立集的混合精确算法。该算法首先通过极大独立集将原图的着色问题转化为子图的着色问题，然后对子图的着色问题利用顶点选择和颜色传播思想解决。对算法进行了大量随机算例和标准算例的测试。对随机图的测试结果显示，算法能够解决所有80个顶点以内的随机图的着色问题。对GCI国际标准算例的测试结果显示，该算法对已解决算例和未解决算例均取得了非常好的效果。通过与其它算法的比较，认为本文提出的算法是一个高效且具有潜力的算法。