图的点染色和边染色

出处：按学科分类—自然科学总论 北京出版社《现代科技综述大辞典上》第28页（4555字）

在组合论中常借用颜色使研究对象具有某特征或作出某种分类，“涂色”常泛指没有附加条件地将色分派给研究对象。

典型问题如：正方形4顶点用黑白2色任意涂色，可有6种不同图象(全白、全黑、3白1黑、3黑1白、2白2黑同色相邻或相间)。完全图K6的边红蓝2色任意涂色，必有同色边的K₃(拉姆齐Ramsey数R(3，3)=6)。

图论中研究对象(点和边)的色分派常要求满足附加条件，故改术语为染色。

图G=(V，E)，｜V｜=n，｜E｜=m，(n个点，m条边)。

除非特别标明，一般研究无多重边，无自环的标之为简单图的图，本文也是。图G的顶点染色，是对每一点指派一种颜色，使相邻接的点都有不同的色(或称正常点染色，经常简称染色)。

如给定k种色，可以用λ(λ≥k)种色作出正常点染色，就说G是k－可(点)染色，使G有正常染色的最小色种数称为(点)色数，记为x(G)，对于k－可染色图，必有x≤k，如记x(G)=k，则说G是k色的。

求图的色数意义深远。

众所周知的四色猜想说：在平面(球面)上(每个国家认为由一个单连通区域表出，两国相邻即有一段公共边界线，任何地图能够只用4种色染色，使没有两邻国有相同色。图论中采用改造成对偶图的方法：每个区域缩为1个“代表点”，2个有公共边界的代表点之间连接一条“边”，平面地图就对偶了1个由“代表点”和“边”组成的平面图(地图的对偶图)。这个对偶图的点染色就是地图的面染色。

四色猜想的本意就是认为：每一个可平面图是4－可点染色的，早期研究这猜想的有莫比乌斯(Möbius，1840)、格思里(Guthrie，1850)、德·摩根(De Morgan，1850)。

肯普(Kempe，1879)曾给出猜想的许多错误“证明”中的第1个“证明”，实际上，Kempe的链路方法证得的是“五色定理”。希伍德(Heawood，1890)指出了他的错误，直到1976年美国的阿倍(K．Appel)、黑肯(W．Hakan)和考奇(J．Koch)3人用电子计算机证明了四色定理，有不少学者认为首开了机器证明的范例。也有不少学者认为不严密，不予承认。总之，还有相当一些人仍在探索简明的证明。当然，确定点色数是基本问题。已求得：x(K_n)=n，x(K_n－e)=n－1，，x(K_p，q)=2，x(C_2i)=2，x(C_2i+1)=3。科尼希(König)1931年证明了一个图是双色的，当且仅当它不含奇圈。但是3－可色图的特征还没有解决。

已经求得一些估界，记Δ为最大的点度粗略的有x≤1+Δ。

对于Δ≥3的图，估式x≤Δ(除了K_Δ+1作为G的分支以外)成立。由贝克霍夫(Birkhoff，1912)作为冲击四色猜想而引入的色多项式也是求色数的工具，记P(G，λ)为一个标定图至多用λ种色(点)染色的不同方式个数。它也是λ的一个整系数多项式。

当λ＜x(G)时，P(G，λ)=0，使P(G，λ)＞0的最小正整数就是x(G)。四色猜想断言：可平面图G，P(G，λ)＞0。易于看出P(K_n，λ)=λ(λ－1)…(λ－n+1)=λ_(n)，。任何一个非完全图G，若u，v是非邻接点，则

P(G，λ)=P(G+uv，λ)+P(G_u=v，λ)

式中G+uv表示添加uv边后的图，G_u=v表示等同u、v二点所得的图，它变成n－1个点的图了。

多次递归使用P(G，λ)就等于若干完全图的色多项式之和。与此逐次加边方式相仿，还有逐次减边方式求P(G，λ)的，如G中有邻接边uv，P(G，λ)=P(G－uv，λ)－P(G_u=v，λ)，多次递归使用，P(G，λ)等于若干孤立点图色多项式的代数和。

色多项式系数表征了图的结构之间的内在性质：P(G，λ)=λⁿ－mλ^n－1+…+(－1)^n－pa_pλ^p，即n个点m条边p个连通分支的图的色多项式必是首系数为1，λ^n－1系数为－m，以下均正负交替。最低非零次项是λ^p，里德(R．C．Read，1968)猜想：P(G，λ)的系数绝对值是单峰性的，即先上升后下降。

同构的图，色多项式相同，反之，不一定。已证出，一个有n个点的图G是一棵树当且仅当P(G，λ)=λ(λ－1)^n－1。

而4个点的树就有不同构的P₄和星K_1，3，一般的具有相同色多项式的图的特征还没有解决。另一难题是如何判断多项式是否是某个图的色多项式。

色多项式作为研究色数的工具还有很多潜在的成果待开拓，图论作为离散数学范畴，没有“万能”或通用的研究手段，如数学分析中有成熟手段：极限，微分，积分，级数等。图论中邻接矩阵特征多项式，再借用线性代数和近世代数中已有成果，发展成称为“代数图论”的分支。

色多项式研究正在发展中，点染色另外的研究方向有唯一可染色图问题［用x(G)种色对V(G)作的色划分是相同的］、色临界问题［对G中每一点v，都有x(G－v)=xLG)－1称为临界图］。

在理论计算机科学研究领域，算法复杂性是基本概念，它对现实的指导意义深远。只有运算次数是求解问题规模n的多项式，这个算法才是可行的，不然发生指数爆炸，一般都效果不好，尤其是一类称之为NP－完全型难题在现在计算机结构体系下是难以找到有效算法的，已经证明，对任意的图G=(V，E)，欲判断G是不是3－可染色是一个NP－完全问题(斯托克迈耶stockmeyer，1973证出)。

图G=(V，E)的边染色，即对图的每条边指派一种色且使得没有两条邻接边有相同色，G中同色的边集也可称为(色)边独立集(匹配)，使G有边染色的最小色种个数称为边色数，记为x′(G)，记Δ是G的最大度，维津(Vizing)在1964年证出Δ≤x′(G)≤Δ+1，此后称x′(G)=Δ的为第1类图C₁，其余的，归入第2类图C₂。

并引出了对边色数分类的大量研究，已证得属于C₁的图类有：二分图，完全图K_2i等，属于C₂的图类有K_2i+1，C_2i+1等。但通用图的分类还没有找到判据。已有人对143个连通的6个顶点以下的图分类，仅有8个属于C₂，这8个图中有C₃，C₅，K₅，K₅－e等。

厄尔丢斯(Erdös)和威尔逊(wilson)在1977年证明n个点的图中，c₁类图占的比值，随n→∞趋于1，分类问题中还有不少充分性定理，如对于正则图，如m＞Δ·，则G属于C₂类，另一个有趣的结论：四色定理等价于3正则平面图的边色数为3，它显示了“点”染色与“边”染色之间的内在联系。

边色数的另一研究方向是边色临界图，如果G是连通的且属于C₂类，对于任一条边e，有x′(G－e)＜x′(G)，则G称(边色)临界图，或说是Δ－边色临界的，如奇圈C_2i+1是2－边色临界的，K₅－e是4－边色临界的，这方面已证得一些必要条件：如果G是Δ－边色临界的，则G不含割点；记I是G的任意一个边独立集，则x′(G－I)=x′(G)－1；对于满足2≤i≤Δ的每个i，G含有一个i－边色临界子图；如v和w是G中邻接点，则必有d(v)+d(w)≥Δ+2；不存在正则的Δ－边色临界图，满足Δ≥3。

关于边染色又引出不少猜想，贾柯勃逊(Jakobsen，1974)、比耐克(Beineke)和威尔逊(wilson)在1973年猜想(因子分解猜想)：每一个偶数点的边色临界图含有一个1－因子；每一个边色临界图含有一个2－因子(k－因子即每点的度为k的生成子图。

维津在1968年猜想：△－边色临界图必有。

另一研究方向是唯一(边)染色图，即G的边集在x′(G)种色边染色下，色划分是唯一的那些图。此时G也称为x′－唯一边可色图。

对此已证得唯一边可色图的必要条件：(1)每条色边都和其它色的一条边邻接。

(2)记H(α，β)为G中α色和β色的边导出双色子图，则H(α，β)或是开路，或是闭偶圈。(3)满足不等式：

(4)如G还是k－正则图(k≥3))，若G中对任取的一条边插入一个点(一次细分)所得的图记为H，则H是3－临界的，此外还证得仅有的4－边色临界图是K_1，4。

在唯一边可色图研究领域内有不少猜想，猜想(1)每一个平面唯一3－可边染色图，除了K_1，3外，都含一个三角形；猜想(2)非平面的3正则唯一3－边可染色图，只有一个彼得森(peterson)型图P(9，2)，即外圈是依次标点为1，2，…，9的C₉，每点向内延伸一条边，加一个点，相应记为1’，，2’，…，9’，。而且这9个点隔号相连形成另一个C₉：1’3’5’7’9’2’4’6’8’1’；猜想(3)：每一个恰有3个哈密顿圈的3正则图是唯一3－边可染色的。

在边染色问题中，中国学者引入了边－色多项式，记为

Q(G，λ)=λ^m－a₁λ^m－1+a₂λ^m－2－…+(－1)^kakλ^m－k，

其中．d_i为每点的度，(Δ)，N(Δ)为G中三角形个数。

m－k=p(G)，是G的连通分支数。如果两个图点数相同且边色多项式也相同就能得出两个图同构，则说这个图是边色多项式拟色唯一的。已推知边色多项式拟色唯一的图有：P_n；K_n；K_n，n；；T_n(n≤5的树)，而对于点数n＞5的树，其边色多项式Q(T_n，λ)不是拟色唯一的(唐廷载、韩绍岭，1991)。

在点染色、边染色基础上，1965年有人把点和边结合看待，提出了“全染色”概念，一个图的全色数x₂(G)是对图的点、边进行色分配，使既是点染色又是边染色并且点和关联边不同色的最小色种个数，如x₂(K_3，3)=5。比扎特(M．Behzad)1965年猜想：对任何图，x₂(G)≤Δ(G)+2．边染色在电网络，课程表问题，拉丁方构造等领域也获得应用。

关于对任意一个图，实施正常点染色，或边染色的有效算法或近似算法是重要的课题，关于全染色，多重图，超图等元素染色在理论和应用方面还有大量工作等待人们去研究。

。

【参考文献】：

1 Beineke L W，et al．Selected topics in graph theory，1978，103～126

2 Yap H P．London Mathematical Society lecture Note Series，1986，108～887

3 唐廷载，等．数学研究与评论，1991．11(4)∶522

(北京理工大学杨骅飞副教授撰；孙良审)