图顶点着色问题是经典的组合优化问题之一，属于NP难问题，它不论在理论研究还是现实生活中均有重要的价值。在理论方面，图顶点着色是图论的一个重要研究方向，在图论中占有重要的地位，广大学者对它的不断研究与探索极大的推动了现代图论的发展。另一方面，该问题有着广泛的应用背景，如资源分配、超大规模集成电路布线、频率分配等，许多领域的问题都可归结为图顶点着色问题来求解。寻求高效的算法对图着色问题进行求解成为图论工作者及从事工程技术方面的学者研究的一个主要课题。当问题规模较大时，不存在多项式时间内的精确算法，因此在现实应用中，启发式算法的研究成为一个重要的方面。遗传算法作为一种全局随机搜索和优化的启发式算法成为求解该问题的重要分支，它是一种利用自然选择和进化思想在高维空间中寻优的方法，它不一定找到最优点，但能在可接受的时间内找到较优解，而找到的解往往已能满足实际应用的要求。在算法的设计过程中多处采取了贪心策略，每一步贪心选择都能得到局部最优解，实验表明，这对于弥补遗传算法局部搜索能力较差的问题有较大帮助。本文对大量的算例进行了实验，结果表明，文中设计的遗传算法对图顶点着色问题的求解具有较好的搜索能力。