【图的点染色和边染色】
拼译：vertex-colourings and edgee-colourings of graphs
在组合论中常借用颜色使研究对象具有某特征或作出某种分类，“涂色”常泛指没有附加条件地将色分派给研究对象。典型问题如：正方形4顶点用黑白2色任意涂色，可有6种不同图象(全白、全黑、3白1黑、3黑1白、2白2黑同色相邻或相间)。完全图K6的边红蓝2色任意涂色，必有同色边的K3(拉姆齐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(Kn)=n，x(Kn－e)=n－1，
，x(Kp，q)=2，x(C2i)=2，x(C2i+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(Kn，λ)=λ(λ－1)…(λ－n+1)=λ(n)，
。任何一个非完全图G，若u，v是非邻接点，则P(G，λ)=P(G+uv，λ)+P(Gu=v，λ)
式中G+uv表示添加uv边后的图，Gu=v表示等同u、v二点所得的图，它变成n－1个点的图了。多次递归使用P(G，λ)就等于若干完全图的色多项式之和。与此逐次加边方式相仿，还有逐次减边方式求P(G，λ)的，如G中有邻接边uv，P(G，λ)=P(G－uv，λ)－P(Gu=v，λ)，多次递归使用，P(G，λ)等于若干孤立点图色多项式的代数和。色多项式系数表征了图的结构之间的内在性质：P(G，λ)=λn－mλn－1+…+(－1)n－papλp，即n个点m条边p个连通分支的图的色多项式必是首系数为1，λn－1系数为－m，以下均正负交替。最低非零次项是λp，里德(R．C．Read，1968)猜想：P(G，λ)的系数绝对值是单峰性的，即先上升后下降。同构的图，色多项式相同，反之，不一定。已证出，一个有n个点的图G是一棵树当且仅当P(G，λ)=λ(λ－1)n－1。而4个点的树就有不同构的P4和星K1，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类图C1，其余的，归入第2类图C2。并引出了对边色数分类的大量研究，已证得属于C1的图类有：二分图，完全图K2i等，属于C2的图类有K2i+1，C2i+1等。但通用图的分类还没有找到判据。已有人对143个连通的6个顶点以下的图分类，仅有8个属于C2，这8个图中有C3，C5，K5，K5－e等。厄尔丢斯(Erdös)和威尔逊(wilson)在1977年证明n个点的图中，c1类图占的比值，随n→∞趋于1，分类问题中还有不少充分性定理，如对于正则图，如m＞Δ·
，则G属于C2类，另一个有趣的结论：四色定理等价于3正则平面图的边色数为3，它显示了“点”染色与“边”染色之间的内在联系。边色数的另一研究方向是边色临界图，如果G是连通的且属于C2类，对于任一条边e，有x′(G－e)＜x′(G)，则G称(边色)临界图，或说是Δ－边色临界的，如奇圈C2i+1是2－边色临界的，K5－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－边色临界图是K1，4。在唯一边可色图研究领域内有不少猜想，猜想(1)每一个平面唯一3－可边染色图，除了K1，3外，都含一个三角形；猜想(2)非平面的3正则唯一3－边可染色图，只有一个彼得森(peterson)型图P(9，2)，即外圈是依次标点为1，2，…，9的C9，每点向内延伸一条边，加一个点，相应记为1’，，2’，…，9’，。而且这9个点隔号相连形成另一个C9：1’3’5’7’9’2’4’6’8’1’；猜想(3)：每一个恰有3个哈密顿圈的3正则图是唯一3－边可染色的。
在边染色问题中，中国学者引入了边－色多项式，记为Q(G，λ)=λm－a1λm－1+a2λm－2－…+(－1)kakλm－k，
其中
．di为每点的度，
(Δ)，N(Δ)为G中三角形个数。m－k=p(G)，是G的连通分支数。如果两个图点数相同且边色多项式也相同就能得出两个图同构，则说这个图是边色多项式拟色唯一的。已推知边色多项式拟色唯一的图有：Pn；Kn；Kn，n；
；Tn(n≤5的树)，而对于点数n＞5的树，其边色多项式Q(Tn，λ)不是拟色唯一的(唐廷载、韩绍岭，1991)。
(北京理工大学杨骅飞副教授撰；孙良审)