平面图着色问题在图论和组合优化中具有重要地位，同时在很多其它领域具有广泛的应用。它的研究起源于著名的四色猜想(即至多用四种颜色给平面或球面上的地图着色，使相邻的区域着上不同的颜色)。虽然K．Appel，W．Haken和J．Koch在1976年借助计算机给出了四色猜想证明，但该证明仅仅给出了理论结果，对于具体平面图的实际4-着色问题并没有帮助。因此，平面图的着色算法，特别是正常4-着色算法，一直是图论研究的热点之一，然而该问题自身的复杂性决定此类算法的研究异常困难。本文首先介绍了平面图着色理论的发展和相关成果，接着深入探讨了乌力吉教授提出的4-着色布尔方程组的性质，然后给出了两种极大平面图4-着色算法：1．在第三章中，我们给出了求极大平面图4-着色全部解算法。该算法与以往算法相比较，具有两大优势：其一，得到一个极大平面图正常4-着色的全部解；其二，由于算法没有试探步骤，避免了无谓计算，提高了算法效率。虽然该算法得到了任意平面图的全部正常4-着色方案，但它的计算量在理论上是边数的指数函数。2．在第四章中，为了克服上述缺点，我们给出了快速求极大平面图一个正常4-着色的加权算法，利用它可以迅速求得极大平面图的一个正常4-着色．该算法的复杂度是边数的线性函数。