一、 图的着色的基本概念
已知一个图g和m>0种颜色，在只准使用这m种颜色对g的结点着色的情况下，是否能使图中任何相邻的两个结点都具有不同的颜色呢?这个问题称为m-着色判定问题。在m-着色最优化问题则是求可对图g着色的最小整数m。这个整数称为图g的色数。
对于图着色的研究是从m—可着色性问题的著名特例——四色问题开始的。这个问题要求证明平面或球面上的任何地图的所有区域都至多可用四种、颜色来着色，并使任何两个有一段公共边界的相邻区域没有相同的颜色。这个问题可转换成对一平面图的４－着色判定问题(平面图是一个能画于平面上而边无任何交叉的图)。将地图的每个区域变成一个结点，若两个区域相邻，则相应的结点用一条边连接起来。图46．1显示了一幅有5个区域的地图以及与该地图对应的平面图。多年来，虽然已证明用5种颜色足以对任一幅地图着色，但是一直找不到一定要求多于4种颜色的地图。直到1976年这个问题才由爱普尔(k．i．apple)，黑肯(w．haken)和考西(j．koch)利用电子计算机的帮助得以解决。他们证明了4种颜色足以对任何地图着色。在这一节，不是只考虑那些由地图产生出来的图，而是所有的图。讨论在至多使用m种颜色的情况下，可对一给定的图着色的所有不同方法。
假定用图的邻接矩阵graPh(1：n，1：n)来表示一个图g，其中若(i，j)是g的一条边，则graPh(i，j)=true，否刷graPh(i，j)=false。因为要拟制的算法只关心一条边是否存在，所以使用布尔值。颜色用整数1，2，…，m表示，解则用n—元组((1)，…，x(n))来给出，其中x(i)是结点i的颜色。此算法使用的基本状态空间树是一棵度数为m，高为n+1的树。在i级上的每一个结点有m个儿子，它们与x(i)的m种可能的赋值相对应，1≤i≤n。在n+1级上的结点都是叶结点。图46．2给出了n＝3且m＝3时的状态空间树。
二、图的着色的基本算法
[算法]： 找一个图的所有m—着色方案 [动画]
procedure mcoloring(k)
／／这是图着色的一个递归回溯算法。图g用它的布尔邻接矩阵graPh(1：n，1：n)表示。它计算并打印出符合以下要求的全部解，把整数1，2，…，m分配给图中各个结点且使相邻近的结点的有不同的整数。k是下一个要着色结点的下标。／／
global integer m，n，x(1：n)boolean graPh(1；n，1：n)
integer k
loop ／／产生对x(k)所有的合法赋值。／／
call nextvalue(k)。//将一种合法的颜色分配给x(k)／／
if x(k)＝0 then exit endif ／／没有可用的颜色了／／
if k=n
then print(x) ／／至多用了m种颜色分配给n个结点／／
else call mcoloring<k+1) ／／所有m—着色方案均在此反复递归调用中产生／／
endif
repeat
end mcoloring
在最初调用call mcoloring(1)之前，应对图的邻接矩阵置初值并对数组x置0值。
在确定了x(1)到x(k-1)的颜色之后，过程nextvalue从这m种颜色中挑选一种
符合要求的颜色，并把它分配给x(k)，若无可用的颜色，则返回x(k)＝0。
[算法]： 生成下一种颜色 [动画]
procedure nextvalue(k)
／／进入此过程前x(1)，...，x(k一1)已分得了区域[o，m]中的整数且相邻近的结
点有不同的整数。本过程在区域[0，m]中给x(k)确定一个值：如果还剩下一
些颜色，它们与结点k邻接的结点分配的颜色不同，那末就将其中最高标值的
颜色分配给结点k；如果没剩下可用的颜色，则置x(k)为0 ／／
global integer m，n，x(1：n)boolean graPh(1：n，1：n)
integer j，k
loop
x(k)+(x(k)+1)mod(m+1) ／／试验下一个最高标值的颜色／／
if x(k)＝0 then return endif //全部颜色用完／／
for jß1to n do ／／检查此颜色是否与邻近结点的那些颜色不同／／
if graPh(k，j) and ／／如果(k，j)是一条边／
x(k)=x(j) ／／并且邻近的结点有相同的颜色／／
then exit endif
repeat ／／否则试着找另一种颜色／／
end nextvalue
该算法的计算时间上界可以由状态空间树的内部结点数 得到。在每个内部结点处，为了确定它的儿子们所对应的合法着色，由nextvalue所花费的时间是 (mn)。因此，总的时间由 所限界。
图46．3显示了一个包含四个结点的简单图。下面是一棵由过程mcoloring生成的
树。到叶于结点的每一条路径表示一种至多使用3种颜色的着色法。