论文摘要
染色问题是图论的重要问题之一。它起源于四色问题的研究。有很强的理论意义和实际意义。目前，随着图的染色问题在现实中被广泛应用，它逐渐成为众多学者研究的重要领域之一。是图论研究中一个很活跃的课题，各类染色问题被相继提出并加以发展、应用。 本文主要研究平面规则网格——方形网格（square mesh）、六角网格（hexagonal mesh）和蜂巢网格（honeycomb mesh）的全染色问题和完备染色问题以及不含4-圈、5圈及相邻3-圈且非3-可选的平面图的选色问题。 首先，根据平面规则网格的结构特性，构造性地给出了方形网格、六角网格和蜂巢网格的全染色方案和完备染色方案，并根据所给出的全染色方案，提出了解决这三种平面规则网格全染色问题的全染色算法，这三种算法可以在多项式时间内完成对这三种平面规则网格的全染色，时间复杂度为O（n2）：证明了这三种平面规则网格的全色数为其最大顶点度数加1；方形网格、六角网格的完备色数为其最大顶点度数加3；蜂巢网格的完备色数为其最大顶点度数加4，染色方案是最优的。 其次，对于Montassier等人给出的不含4-圈、5圈及相邻3-圈且非3-可选的平面图给出了新的构造。2006年，Montassier等构造了一个包含506个顶点不含4-圈、5圈及相邻3-圈且非3-可选的平面图（Bordeaux 3-color conjecture and 3-choosability．Discrete Mathematics，306（6）（2006）：573-579），推翻了Bordeaux 3-色猜想：所有不含5-圈和相交3-圈的平面图是3-可选的。本文构造了一个具有相同性质且包含更少顶点的平面图，这个平面图仅包含380个顶点，目前是含最少点的不含4-圈、5圈及相邻3-圈且非3-可选的平面图。