1
§ 6.5 染色应用举例—求图的边色数及色数的算法
一、排课表问题—求二部图的正常 )(Gχ′ 边染色
1,问题,有 m 位教师
m
xxx,,,
21
null,n 个班级
n
yyy,,,
21
null 。教师 x
i
每周需要给班级 y
j
上
p
ij
次（节）课。要求制订一张周课时尽可能少的课程表。
2,图论模型,构造二部图 ),( YXG =,其中 X＝ {
m
xxx,,,
21
null },Y＝ {
n
yyy,,,
21
null }，
顶点
i
x 与
j
y 之间连
ij
p 条边。
一个课时的安排方案对应于二部图 G 的一个匹配。排课表问题等价于：将 E(G)划分成一些匹配，使得匹配的数目尽可能地少。
按 )(Gχ′ 的定义，这个最小的数目便是 )(Gχ′ 。由定理 6.2.1,() ()GGχ′ =Δ 。因此，
排课表问题等价于：求二部图 G 的边正常 )(GΔ 染色。
如§ 6.1 中所述，虽然求简单图的正常（ 1+Δ ）边染色存在多项式时间算法，但求简单图 G 的边色数 )(Gχ′ 及其相应的正常边染色是一个 NPC 问题
[28]
。尽管如此，求二部图的边正常 Δ 染色却有多项式时间算法。求图的边色数的近似算法可参考文献 [29]~[51]。
[28] I,Holyer,The NP-completeness of edge-coloring,SIAM J,Computing,10,4(1981),718-720,
[29] E,Petrank,The hardness of approximation,gap location,Computational Complexity,4
(1994),133-157,
[30] D,Leven and Z,Galil,NP completeness of finding the chromatic index of regular graphs,J,
Algorithms,4(1983) 35-44,
[31] P,Crescenzi,V,Kann,R,Silvestri,and L,Trevisan,Structure in approximation classes,SIAM
J,Comp.,28 (1999),1759-1782,
[32] J,Misra and D,Gries,A constructive proof of Vizing's theorem,Inform,Process,Lett,41
(1992),131-133,
[33] O,Terada,and T,Nishizeki,Approximate algorithms for the edge-coloring of graphs,Trans,
Inst,Eletron,Commun,Engr,Japan J65-D,11(1982),1382-1389,
[34] M,Chrobak,and T,Nishizeki,Improved edge-coloring algorithms for planar graphs,J,
Algorithms,11(1990),102-116,
[35] I,Caragiannis,A,Ferreira,C,Kaklamanis,S,Perennes,P,Persiano and H,Rivano,
Approximate constrained bipartite edge coloring,Discrete Applied Mathematics,143(2004),54-61
[36] M,R,Salavatipour,A polynomial time algorithm for strong edge coloring of partial k-trees,
Discrete Applied Mathematics,143(2004),285-291,
[37] D.A,Grable,A,Panconesi,Nearly optimal distributed edge coloring in O (log log n) rounds,
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms,January,
(1997),278–285,
[38] Yijie Han,Weifa Liang and Xiaojun Shen,Very fast parallel algorithms for approximate edge
coloring,Discrete Applied Mathematics,108(2001),227-238,
[39] M,Fürer and B,Raghavachari,Parallel edge coloring approximation,Parallel Process,Lett.,
6 (1996),321–329,
2
[40] H.J,Karloff and D.B,Shmoys,Efficient parallel algorithms for edge coloring problems,J,
Algorithms 8 (1987),39–52,
[41] W,Liang,Fast parallel algorithms for the approximate edge-coloring problem,Inform,
Process,Lett,56 (1995),333–338,
[42] W,Liang,X,Shen and Q,Hu,Parallel algorithms for the edge-coloring and edge-coloring
update problems,J,Parallel Distrib,Comput,32 (1996),66-73,
[43] R,Motwani,J,Naor and M,Naor,The probabilistic method yields deterministic parallel
algorithms,J,Comput,System Sci,49 (1994),478-516,
[44] D,Bertsimas,C-P,Teo,and R,Vohra,On dependent randomized rounding algorithms,Proc,
5th Int,Conf,on Integer Prog,and Combinatorial Optimization,Lecture Notes in Comput,Sci,
1084,Springer-Verlag,(1996),330-344,
[45] M.K,Goldberg,Edge-colorings of multigraphs,recoloring technique,J,Graph Theory,
8(1984),123-127,
[46] D.S,Hochbaum,T,Nishizeki and D.B,Shmoys,Better than,Best Possible” algorithm to
edge color multi graphs,Journal of Algorithms,7(1986),79-104
[47] T,Nishizeki and K,Kashiwagi,On the 1.1 edge-coloring of multigraphs,SIAM J,Disc,
Math.,3(1990),391-410,
[48] J,Kahn,Asymptotics of the chromatic index for multigraphs,Journal of Combinatorial
Theory (Ser,B),68(1996),233-254,
[49] X,Zhou H,Susuki,and T,Nishizeki,A linear algorithm for edge-coloring series-parallel
multigraphs,J,Algorithms,20(1996),174-201,
[50] X,Zhou H,Susuki,and T,Nishizeki,An NC parallel algorithm for edge-coloring
series-parallel multigraphs,J,Algorithms,23(1997),359-374,
[51] B,Berger and J,Rompel,Simulating (log
c
n)-wise independence in NC,J,ACM 38 (1991),
1026–1046,
3,求二部图 ),( YXG = 的边正常 )(GΔ 染色的算法
z 算法思想,给 G 添加必要的顶点使得 |||| YX =,再添加必要的边使得 G 成为 )(GΔ 正则二部图,所得图记为
*
G,然后反复运用匈牙利算法求
*
G 的完美匹配。 由第 3 章 K?nig
定理，
*
G 存在完美匹配。每求出
*
G 的一个完美匹配，便可用一种颜色给这个完美匹配的边染色。因为共可求得
*
G 的 )(GΔ 个边不重的完美匹配，故可得
*
G （从而 G）的边正常 )(GΔ 染色。
z 二部图边染色算法,求二部图的边正常 )(GΔ 染色 (求二部图的 )(GΔ 个边不交的匹配 )。
输入：二部图 G=(X,Y)
输出,G 的边正常 )(GΔ 染色（ )(GΔ 个边不交的匹配）
第 0 步：添加顶点使得 |X|=|Y|，所得图记为
*
G 。
第 1 步：若 )()(
**
GG δ=Δ,令 1=k,转第 3 步；否则，转第 2 步。
3
第 2 步：取 Xx ∈
0
,Yy ∈
0
，使得 )(min)(
**
0 i
G
Xx
G
xdxd
i
∈
=,)(min)(
**
0 i
G
Yy
G
ydyd
i
∈
=,令
00
**
,yxGG +=,转第 1 步。
第 3 步：任取
*
G 的一个匹配 M。
第 4 步：若 X 已 M 饱和，则输出当前的完美匹配，转第 7 步；否则取 X 中一个 M 不饱和点 u，置 }{,uS =,φ=:T 。
第 5 步：在 TSN \)( 中取一点 y,
第 6 步：若 y 是 M 饱和的，则存在 Myz∈,置 }{,zSS ∪=,}{,yTT ∪=,转第 5 步；
否则，存在一条 M 可扩路 P ),( yu,置 )(,PEMM ⊕=,转第 4 步。
第 7 步：若 Δ=k,则停止；否则，令 1,+= kk,MGG \:
**
=,转第 3 步。
设 ||||X Y≥ 。因匈牙利算法的时间复杂性为
3
(| | )OX,而第 1 步和第 2 步的加边循环不超过 Δ?|| X 次，故该算法是多项式时间算法。
4,带有约束的排课表问题
设学校每周有 l 节课，安排在一张有 p 节课时的课表中（前面的方法求得一个 Δ 节课时的课表） 。这样，平均每一课时要上
p
l
节课，因此需要
p
l
间教室。比如,510=l,
20=p,则需要 26
20
510
=
=
p
l
间教室。
问题,可否在一张有 p 节课时的课表里安排 l 节课,使得在一节课时内至多用
p
l
间教室？
下面的引理见第 3 章习题。
引理 6.5.1 设 M 和 N 是图 G 的两个无公共边的匹配，并且 |||| NM >,则存在 G 的无公共边的匹配 M′和 N′，使得 1||||?=′ MM,1|||| +=′ NN,且 NMNM ∪∪ =′′ 。
定理 6.5.1 若图 G 是一个二部图，且 ()p G≥Δ,则 G 中存在 p 个无公共边的匹配
p
MMM null,,
21
，使得
p
MMME ∪null∪∪
21
=,且对每个 ),,2,1( pii null= 均有
≤≤
p
G
M
p
G
i
)(
||
)( εε
。
证明,因图 G是二部图,故由本章定理 6.1.1,边集 )(GE 可划分为 Δ 个匹配
Δ
′′′ MMM,,,
21
null,
因而对任何 )(Gp Δ≥,G 中存在 p 个无公共边的匹配,,,,
21 Δ
′′′ MMM null
p
MM ′′
+Δ
,,
1
null （其中 φ=′==′
+Δ p
MM null
1
）,使得
∪
p
i
i
MGE
1
)(
=
′= 。对这些匹配反复运用引理 6.5.1，便可得到满足定理要求的匹配。证毕。
这个定理对前述带约束排课表问题给出了肯定回答。 同时也给出了求所需教室数最少的
p 课时课表的方法：先按二部图边染色算法求出相应二部图的一个正常 )(GΔ 边染色，然后
4
反复运用引理 6.5.1 对其进行调整，最终使得染不同颜色的两个边集所含边数至多相差 1。
例 6.5.1 设有 4 个教师 x
1
,x
2
,x
3
,x
4
和 5 个班级 y
1
,y
2
,y
3
,y
4
,y
5
，教学矩阵 )(
ij
tT = 表示如下,
=
11000
01110
01010
01102
4
3
2
1
54321
x
x
x
x
yyyyy
T
问,（ 1）课表至少需要几课时？
（ 2）按二部图边染色算法给出一个课时数最少的课表。
（ 3）在课时数最少的前提下，给出需教室数最少的课表方案。
解：构造二部图如下图 1,
图 1 图 2
由于 4)( =Δ G,故课表至少需 4 课时。
执行二部图边染色算法得 G 的 4 个边不交的匹配 (如图 2)。 相应的一个 4 课时课表如下,
教师 课时
1 2 3 4
x
1
y
1
y
1
y
3
y
4
x
2
y
2
y
4
x
3
y
3
y
4
y
2
x
4
y
4
y
5
按这张课表安排，需 4 个教室。但因 11)( =Gε,3
4
11
=
=
p
ε
，由定理 6.4.1，可排出一张只需 3 个教室的 4 课时课表。事实上，将教师
4
x 在第 1 课时的课调到第 3 课时而将教师
2
x 在第 3 课时的课与第 1 课时对调即可。从二部图的匹配上来看，是将第 1 课时和第 3 课时对应的匹配施行了一次引理 6.4.1 的操作。一张只需 3 个教室的 4 课时课表如下,
教师 课时
1 2 3 4
x
1
y
1
y
1
y
3
y
4
x
2
y
4
y
2
x
3
y
3
y
4
y
2
x
4
y
5
y
4
x
4
x
3
x
2
x
1
y
1
y
2
y
3
y
4
y
5
x
4
x
3
x
2
x
1
y
1
y
2
y
3
y
4
y
5
5
二、点染色的应用及正常 )(Gχ 点染色的求法
1．应用背景举例
（ 1）考试安排问题
某校有 n 门选修课
n
LLL,,,
21
null 需进行期末考试,同一个学生不能在同一天里参加两门或两门以上课程的考试。试问：该校的期末考试至少需要几天？如何安排？
图论模型：构造图 G＝ (V,E)如下,=)(GV {
n
LLL,,,
21
null },)(GELL
ji
∈ 当且仅当课程
i
L 和
j
L 被同一学生选修。
将同一天的考试课程在 G 中对应的顶点染同一种色，则考试安排相当于对 G 进行顶点正常染色。所求最少天数即为 G 的点色数 )(Gχ 。问题化为：求图 G 的正常 )(Gχ 点染色。
（ 2）电视频道分配问题
某地区有 n 家电视发射台
n
TTT,,,
21
null,主管部门给每家电视台分配一个发射频道。为排除同频干扰，使用相同频道的发射台之间相距必须大于一定的距离 d。试问：该地区至少需要多少个频道？如何分配？
图论模型：构造图 G＝ (V,E)如下,=)(GV {
n
TTT,,,
21
null },)(GETT
ji
∈ 当且仅当发射台
i
T 和
j
T 的距离不超过 d。
考虑 G 图的正常点染色。易见染同一种色的顶点可分配给同一频道。反之，按要求分配一个频道，相当于给 G 中相应的顶点染同一种色。因此，频道分配相当于对 G 进行顶点正常染色。所求最少频道数即为点色数 )(Gχ 。问题化为：求图 G 的正常 )(Gχ 点染色。
（ 3）储藏问题
某公司生产 n 种化学品
n
CCC,,,
21
null,其中某些制品不能存放在同一个仓库中。问至少需要多少个仓库？如何分配存放？
图论模型：构造图 G＝ (V,E)如下,=)(GV {
n
CCC,,,
21
null },)(GECC
ji
∈ 当且仅当制品
i
C 和
j
C 不能放在同一仓库中。
若干制品可放在同一仓库当且仅当它们在 G 中对应的顶点可染同一种色。可见给这些产品分配仓库相当于对 G 进行正常点染色。所需的最少仓库数即为 G 的点色数 )(Gχ 。问题化为：求图 G 的正常 )(Gχ 点染色。
对既不是完全图又不是奇圈的图 G,利用 Brooks定理的证明可以得到求 G的顶点 (G)Δ -
正常染色的一个有效算法
[116]
。但是，在一般情况下,(G)Δ 与 )(Gχ 并不相等。求任意图的正常 )(Gχ 点染色是一个 NPC 问题
[116]
，目前没有多项式时间精确算法，仅有一些适用于小规模问题的非多项式时间算法和一些多项式时间近似算法。遗憾的是，迄今为止找到的多项式时间近似算法其近似比都不等于常数。可见，从计算复杂性的角度来看，图的点染色问题是如此困难，以至于连近似比等于常数的多项式时间近似算法都难以找到。实际上，已经证
6
明，如果存在多项式时间染色算法使得对每个图 G 都可使用不多于 2(G)χ 种色进行正常顶点染色，则必定存在 G 的 (G)χ 顶点染色有效算法
[117][118]
。这表明，对图的点染色问题，找近似比等于常数的多项式时间近似算法与找 (G)χ 顶点染色的（有效）精确算法一样困难。
下面介绍点染色问题的几种非多项式时间算法和简单的近似算法。 更多的算法可参见文献 [52]~[115]，其中 [52]~[58]是与图的点染色算法有关的专著,[59]~[72]研究图的点染色问题的各种精确算法,[73]~[89]研究图的点染色问题的近似算法及其性能，在不同条件下给出了较低近似比的染色算法,[90]~[111]将邻域方法、禁忌搜索和局部搜索方法、模拟退火法、
人工神经网络、遗传算法、蚁群算法等方法以及其它一些启发式方法用于图的点染色问题。
[112]-[115]讨论点染色的相关计算复杂性问题。
[52] G,Chartrand,O,R,Oellermann,Applied and Algorithmic Graph Theory,McGraw-Hill,Inc.,
New York,(1993),283-310,
[53] M.R,Garey and D.S,Johnson,Computers and Intractibility,A Guide to the Theory of
NP-Completeness,Freeman,New York,1979,
[54] D.S,Hochbaum,Approximation Algorithms for NP-hard Problems,International Thomson
Publishing Inc.,1997 (影印本,NP 难解问题的近似算法，世界图书出版公司 )。
[55] N,Christofides,Graph Theory,An Algorithmic Approach,Academic Press,New York,
(1990),58-78,
[56] S,Even,Algorithmic Combinatorics,Macmillan,New York,1973,
[57] R,Gould,Graph Theory,Benjamin Cummings,Menlo,Park,CA(1988),
[58] D.W,Matula,G,Marble,and J.D,Isaacson,Graph colouring algorithms,in Graph Theory
and Computing (Read Ed.),Academic Press,New York,(1972) 109-122,
[59] D,Brelaz,New methods to color the vertices of a graph,Communications of the Association
for Computing Machinery,22(1979),251-256,
[60] E.C.Sewell,An Improved algorithm for exact graph coloring,in,Cliques,Coloring and
Satisfiability”,(DIMACS Series in Discrete Mathematics and Theoretical Computer Science),
26 (1996),359-373,American Mathematical Society,Providence,RI,USA,
[61] D,Eppstein,Small maximal independent sets and faster exact graph coloring,Journal of
Graph Algorithms and Applications,7(2) (2003),131-140,
[62] N,Christofides,An algorithm for the chromatic number of a graph,The Computer Journal,
14(1971),38-39,
[63] D,G,Corneil and B,Graham,An algorithm for determining the chromatic number of a graph,
SIAM Journal on Computing,2(1973),211-218,
[64] D,Kirovski and M,Potkonjak,Efficient coloring of a large spectrum of graphs,In DAC '98,
Proceedings of the 35th annual conference on Design automation,(1998),427-432,ACM Press,
New York,NY,USA,
[65] Ojvind Johansson,Simple distributed 1Δ+ -coloring of graphs,Information Processing
Letters,70(1999),229-232,
[66] I.M,Diaz and P,Zabala,A branch-and-cut algorithm for graph coloring,(2002),55-62,Ithaca,
New York,USA,
7
[67] M,Caramia and P,Dell'Olmo,Bounding vertex coloring by truncated multistage branch and
bound,Networks,44(4) (2004),231-242,
[68] M,Kubale and B,Jackowski,A generalized implicit enumeration algorithm for graph
coloring,Communications of the ACM,28 (1985),412-418,
[69] A,Mehrotra and M,Trick,A column generation approach for graph coloring,INFORMS
Journal On Computing,8(4) (1996),344-354,
[70] S.R,Vegdahl,Using node merging to enhance graph coloring,In PLDI '99,Proceedings of
the ACM SIGPLAN 1999 conference on Programming language design and implementation,
(1999),150-154,ACM Press,New York,NY,USA,
[71] F,Herrmann and A,Hertz,Finding the chromatic number by means of critical graphs,
Journal of Experimental Algorithmics,7(2002),p10,
[72] G.A,Kochenberger,F,Glover,B,Alidaee,and C,Rego,An unconstrained quadratic binary
approach to the vertex coloring problem,Annals of Operations Research,139(1) (2005),229-241,
[73] A,Wigderaon,improving the performance guarantee for approximate graph coloring,Journal
of the ACM,30(1983),729-735,
[74] B,Berger and J,Rompel,A better permance guarantee for approximate graph coloring,
Algorithmica,5(1990),459-466,
[75] M,M,Halldórsson,A still better performance guarantee for approximate graph coloring,
Information Processing Letters,45(1993),19-23,
[76] M,Bellare,O,Goldreich,and M,Sudan,Free bits,PCPs and non-approximability - towards
tight results,SIAM J,Comp,27(1998),804-915,
[77] A,Blum,and D,Karger,An
3
14
()On
null
-coloring algorithm for 3-colorable graphs,Information
Processing Letters,61(1997),49-53,
[78] L,J,Cowen,W,Goddard,and C,E,Jesurum,Coloring with defect,Proc,8th Ann,
ACM-SIAM Symp,on Discrete Algorithms,ACM-SIAM,(1997),548-557,
[79] R,Duh,and M,Fürer,Approximation of k-set cover by semi-local optimization,Proc,29th
Ann,ACM Symp,on Theory of Comp.,ACM,(1997),256-265,
[80] D,Karger,R,Motwani,and M,Sudan,Approximate graph coloring by semidefinite
programming,J,ACM,45(1998),246-265,或见 Proceedings of the 35
th
Annual IEEE
Symposium on Foundations of Computer Science,(1994),2-13,
[81] M,Krivelevich,and B,Sudakov,Approximate coloring of uniform hypergraphs,Proc,6th
Ann,European Symp,on Algorithms,Lecture Notes in Comput,Sci.,Springer-Verlag,(1998),
477-489,
[82] T,Hofmeister,and H,Lefmann,Approximating maximum independent sets in uniform
hypergraphs,Proc,23rd International Symp,on Mathematical Foundations of Comput,Sci.,
Lecture Notes in Comput,Sci,1450,Springer-Verlag,(1998),562-570,
[83] U,Feige,and J,Kilian,Zero knowledge and the chromatic number,Journal of Computer and
System Sciences,57(2)(1998),187-199,
[84] V,Kumar,Approximating circular arc colouring and bandwidth allocation in all-optical ring
networks,Proc,1st Int,Workshop on Approximation Algorithms for Combinatorial Problems,
Lecture Notes in Comput,Sci.,Springer-Verlag,(1998),147-158,
8
[85] S,Khanna,N.Linial,and S,Safra,On the hardness of approximating the chromatic number,
Proc,2nd Israel Symp,on Theory of Computing and Systems,IEEE Computer Society,(1993),
250-260,
[86] C,Lund,and M,Yannakakis,On the hardness of approximating minimization problems,J,
ACM 41(1994),960-981,
[87] M,V,Marathe,H,Breu,H,B,Hunt III,S,S,Ravi,and D,J,Rosenkrantz,Simple heuristics
for unit disk graphs,Networks,25(1995),59-68,
[88] A,Blum,New Appproximation algorithms for graph coloring,Journal of the ACM,41(1994),
470-516,
[89] A,Blum,Some tools for approximate 3-coloring,In Proceedings 31st IEEE Symposium on
Foundations of Computer Science,pages 554-562,Los Angeles,CA,1990,IEEE Computer
Society,
[90] M,Laguna and R,Martí,A GRASP for coloring sparse graphs,Computational optimization
and applications,19(2) (2001),165-178,
[91] Alon N.,Krivelevich M.,and Sudakov B.,Coloring graphs with sparse neighborhoods,
Journal of Combinatorial Theory,Ser,B,77(1999),73-82,
[92] Morgenstern C,and Shapiro H.,Coloration neighborhood structures for general graph
coloring,In Proceedings of the first annual ACM-SIAM Symposium on Discrete algorithms,
(1990),226-235,Society for Industrial and Applied Mathematics,Philadelphia,PA,USA,
[93] Avanthay C.,Hertz A.,and Zufferey N.,A variable neighborhood search for graph coloring,
European Journal of Operational Research,(2003),
[94] Glass C.A,and Prügel-Bennett A.,A polynomially searchable exponential neighbourhood for
graph colouring,Journal of the Operational Research Society,56(3) (2005),pp,324-330,
[95] Hertz A,and de Werra D.,Using tabu search techniques for graph coloring,Computing,39(4)
(1987),345-351,
[96] González-Velarde J,and Laguna M.,Tabu search with simple ejection chains for coloring
graphs,Annals of Operations Research,117(1-4) (2002),165-174,
[97] Chiarandini M,and Stützle T.,An application of iterated local search to graph coloring,In
Proceedings of the Computational Symposium on Graph Coloring and its Generalizations,edited
by D.S,Johnson,A,Mehrotra,and M,Trick,(2002),112-125,Ithaca,New York,USA,
[98] Fleurent C,and Ferland J.,Object-oriented implementation of heuristics search methods for
graph coloring,maximum clique,and satisfiability,vol,26 of DIMACS Series in Discrete
Mathematics and Theoretical Computer Science,(1996),619-652,American Mathematical
Society,Providence,RI,USA,
[99] D,de Werra,Lausanne,Heuristics for graph coloring,Computing Supplementum,7(1990)
191-208,
[100] Blas A.D.,Jagota A.,and Hughey R.,A range-compaction heuristic for graph coloring,
Journal of Heuristics,9(3) (2003),489-506,
[101] Lewandowski G,and Condon A.,Experiments with parallel graph coloring heuristics and
applications of graph coloring,vol,26 of DIMACS Series in Discrete Mathematics and
Theoretical Computer Science,(1996),309-334,American Mathematical Society,Providence,RI,
USA,
9
[102] Fabrikant A,and Hogg T.,Graph coloring with quantum heuristics,In Proceedings of the
Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on
Innovative Applications of Artificial Intelligence,Edmonton,Alberta,Canada,AAAI Press,(2002),
22-27,
[103] David S,Johnson,Cecilia R,Aragon,Lyle A,McGeoch,and Catherine Schevon,
Optimization by simulated annealing,An experimental evaluation; part II,graph coloring and
number partitioning,Operations Research,39(3):378-406,1991,
[104] Jagota A.,An adaptive,multiple restarts neural network algorithm for graph coloring,
European Journal of Operational Research,93(2) (1996),257-270,
[105] Cutello V.,Nicosia G.,and Pavone M.,A hybrid immune algorithm with information gain
for the graph coloring problem,vol,2723 of Lecture Notes in Computer Science,(2003),
171-182,Springer Verlag,Berlin,Germany,
[106] Glass C.A,and Prügel-Bennett A.,Genetic algorithms for graph colouring,Exploration of
Galinier and Hao's algorithm,Journal of Combinatorial Optimization,7(3) (2003),229-236,
[107] Croitoru C.,Luchian H.,Gheorghies O.,and Apetrei A.,A new genetic graph coloring
heuristic,(2002),63-74,Ithaca,New York,USA,
[108] Galinier P,and Hao J.,Hybrid evolutionary algorithms for graph coloring,Journal of
Combinatorial Optimization,3(4) (1999),379-397,
[109] Eiben A.E.,Hauw J.K.V.D.,and Hemert J.I.V.,Graph coloring with adaptive evolutionary
algorithms,Journal of Heuristics,4(1) (1998),pp,25-46,
[110] Bui T.N,and Patel C.M.,An ant system algorithm for coloring graphs,(2002),83-91,Ithaca,
New York,USA,
[111] D,C,and Hertz A.,Ants can colour graphs,Journal of the Operational Research Society,
48(1997),295-305,
[112] Paschos V.T.,Polynomial approximation and graph-coloring,Computing,70(1) (2003),
41-86,
[113] J,S,Turner,Almost all -colorable graphs are easy to color,Journal of Algorithms,9(1988),
63-82,
[114] Ludek Kucera,Graphs with small chromatic numbers are easy to color,Information
Processing Letters,30(1989),233-236,
[115] Ludek Kucera,The greedy coloring is a bad probabilistic algorithm,Journal of Algorithms,
12(1991),674-684,
2,求图 G 的色数 )(Gχ 及正常 )(Gχ 点染色的算法
z 添边粘合法
添边、粘合操作：给定图 G＝ (V,E)，设 )(,GVvu ∈,且 u,v 在 G 中互不相邻，则
（ 1） 添边操作,给 G 添加边 uv，得图 G′；
（ 2） 粘合操作,将 u,v 两点粘合为一点，并去掉所得的重边，得图 G′′ 。
10
例如,
定理 6.4.2 )}(),(min{)( GGG ′′′= χχχ 。
证明：考虑图 G 的所有可能的正常点染色方案。设 u,v 是 G 中互不相邻的两点，则在 G 中的正常染色下 u,v 的染色有两种可能,u 与 v 同色，或 u 与 v 异色。 G 的使 u 与 v 染同色的正常点染色方案与 G′′ 的正常点染色方案一一对应,而 G 的使 u 与 v 染异色的正常点染色方案与 G′的正常点染色方案一一对应。因此 )}(),(min{)( GGG ′′′= χχχ 。证毕。
添边粘合算法基本思想,对于给定的图 G，若 G 是一个 υ阶完全图，则 ()Gχ υ= 。此时给
G 的每个顶点一个不同的色即可。若 G 不是完全图，则可取两个不相邻顶点 u,v，对 G 进行添边操作和粘合操作，反复进行这个过程，直至获得完全图为止。设最终得到的阶数最小的完全图为
m
K,则由定理 6.4.2,mG =)(χ 。对该完全图进行顶点正常 m 染色，并进行反向操作，便可得图 G 的顶点正常 m 染色。
根据定理 6.4.2，添边粘合算法的运行结果是顶点染色问题的精确解。但添边粘合法的执行过程是一棵二叉树，因此其计算复杂性是指数阶的。
例 6.4.2 求下图 G 的色数，及顶点正常 (G)χ 染色。
解：添边和粘合运算过程如下所示。
u
v
u
v
u v
G
G′
G′′
G
G
11
由于最终得到的阶数最小的完全图为
3
K,故 3)( =Gχ 。 对该
3
K 的 3 个顶点分别染色 1,2，
3。然后反向操作，每次相当于将先前粘合起来的点分开，分出来的两点与原来的点染相同
的颜色。这样得到 G 的一个顶点 3 正常染色如下。
z 规范染色法（极大独立集法）
设 },,,{
21 k
VVV null=? 是图 G 的点 k 染色。若
1
V 是 G 的极大独立集，
2
V 是
1
\ VG 的极大独立集，
3
V 是 )(\
21
VVG ∪ 的极大独立集，……，一般地，
i
V 是
∪
1
1
\
=
i
j
j
VG 的极大独立集
（ ki null,3,2= ）,则称? 是图 G 的 规范 k 染色 （ canonical k-colouring）,
定理 6.4.3 图 G 是顶点可 k 正常染色的当且仅当 G 存在规范 k 染色。
证明：充分性是显然的。
必要性,设 },,,{
21 k
VVV null 是图 G 的一个顶点正常 k 染色,则
k
VVV,,,
21
null 都是 G 的独立集。
若
1
V 不是 G 的极大独立集，则可从
1
\ VV 中调一些顶点进入
1
V,使
1
V 扩大成 G 的极大独立集
)1(
1
V,
k
VVV,,,
32
null 变成
)1()1(
3
)1(
2
,,,
k
VVV null 。然后考虑
)1(
2
V 。若它不是
)1(
1
\ VG 的极大独立集，则可从 )(\
)1(
2
)1(
1
VVV ∪ 中调一些顶点进入
)1(
2
V,将其扩充成
)1(
1
\ VG 的极大独立集
)2(
2
V,
)1()1(
3
)1(
2
,,,
k
VVV null 变成
)2()2(
3
)2(
2
,,,
k
VVV null 。如此类推，最后可得图 G 的规范 k 染色
)()2(
2
)1(
1
,,,
k
k
VVV null 。 证毕。
规范染色法基本思想,求 G 的极大点独立集
1
V,将其顶点都染上色 1；再求
1
\ VG 的极大点独立集
2
V,将其顶点都染上色 2；如此类推，直至染完所有顶点。
规范染色法步骤,
输入：图 G 及其邻接矩阵，输出,G 的顶点正常色划分（独立集划分）,
12
,,,
k
VV Vnull 。
第 0 步,SV=,,1i =,
第 1 步,任取 x S∈,{},( {}) ( )
i
VxTSxNx==?∩：：，转下步。
第 2 步,若 T φ=,输出
i
V,并令
i
SSV=?,转第 4 步；否则，转第 3 步。
第 3 步,任取 y T∈,{},( {}) ( )
ii
VV yT T y Ny==?∩∩，转第 2 步。
第 4 步,若 S φ=,停止；否则，令,1ii= +,转第 1 步。
1
2
3
3
1
12
算法第 1 步至第 4 步反复循环，第 i 次循环得到极大独立集 V
i
。在第 i 次循环中，第 2
步到第 3 步反复循环向 V
i
中添加不相邻顶点，使其成为极大独立集。在算法中,()Nx表示顶点 x 的不相邻顶点集。集合 S 表示除了以得到的极大独立集之外，剩余的顶点集。 T 纪录在形成极大独立集 V
i
的过程中,尚未进入
12
,,,
i
VV Vnull 且与已进入 V
i
的顶点不相邻的顶点之集。算法结束时，得到图 G 的顶点正常色划分（独立集划分）,
12
,,,
k
VV Vnull 。
注,（ 1）这是一种贪婪算法。
（ 2）规范 k 染色一般不唯一。
（ 3）运行一次这个算法能得到图 G 的一种正常顶点染色，但它所用的颜色数未必就是
)(Gχ 。因此该算法是一个近似算法。
（ 4）由定理,G 可用 )(Gχ 种颜色正常顶点染色，则必存在 )(Gχ 规范染色。因此只需从一切规范染色中选出颜色数最少者，即可求得 )(Gχ 。但由于需要枚举所有规范染色才能确定出 )(Gχ,故用该方法求 )(Gχ 不是多项式时间算法，只适用于阶数较小的图。
例 6.4.3 对下图 G，利用规范染色法求其色数 (G)χ 的近似值及相应的顶点染色。
解,G 的一个极大独立集为 },,{
1
cgaV =,
1
\ VG 的一个极大独立集为 },,{
2
fdbV =,
)(\
21
VVG ∪ 的一个极大独立集为 }{
3
eV = 。故 G 可正常 3 顶点染色,3)( ≤Gχ 。相应的顶点 3 正常染色如下所示,
注,对本题所给的图 G，上述过程恰好得到 (G)χ 。事实上，因 G 含有
3
K,因此正常顶点染色至少需要 3 种颜色。从而 3)( =Gχ 。
z 顺序染色法
算法思想：将图 G 的顶点排一个顺序
n
vvv,,,
21
null 。先给顶点
1
v 染上色
1
c 。对顶点
2
v,
从颜色集合 },,,{
321
nullccc 中选取未被
2
v 的邻点使用的编号最小的色来染它。一般地，对顶
a
c
d
bf
e
g
a
c
d
bf
e
g
1
3
1
1
2
2
2
13
点
i
v,从颜色集合 },,,{
321
nullccc 中选取未被
i
v 的邻点使用的编号最小的色给其染色，
ni,,2,1 null= 。
算法步骤,
第 1 步：令 1:=i 。
第 2 步：令 1:=c 。
第 3 步：若对所有 )(
i
vNy∈,颜色 c 未染 y，则令 c 染
i
v,转第 5 步。
第 4 步,1,+= cc,转第 3 步。
第 5 步：若 ni <,则 1,+= ii,转第 2 步；否则，停止。
例,
注,（ 1）顺序染色法是多项式时间算法，时间复杂性为 )(
2
nO 。
（ 2）顺序染色法是一种近似算法，其算法结果（所用颜色数）与顶点的标号顺序有密切关系。比如，对完全二部图 ),(
,
YXK
nn
=,若顶点标号顺序为
nn
yyyxxx,,,,,,,
2121
nullnull,
则算法结果只用两种颜色，是最优解。但若顶点顺序为
nn
yxyxyx,,,,,,
2211
null,则算法结果需 n 种颜色。算法近似比
2
~
*
n
c
c
=,无界！
z Welsh-Powell 算法 (最大度优先算法 )
第 1 步：将图 G 的顶点按度数递减的顺序排列，设为
n
vvv,,,
21
null 。
第 2 步：用第 1 种颜色给
1
v 染色，令 }{:
1
vV
c
=,1:=i 。
第 3 步：若存在与
c
V 中所有点都不相邻的未染色顶点，则找出第一个与
c
V 中所有点都不相邻的未染色顶点 v，转下步；否则 1,+= ii,转第 5 步。
第 4 步：给 v 染上第 i 种色，令 }{,vVV
cc
∪=,转第 3 步。
第 5 步：取尚未染色的顶点中编号最小的顶点 v，令 }{,vV
c
=,转第 3 步。
第 6 步：所有顶点都得到染色时，停止。
例,
v
1
v
3
v
4
v
2
v
6
v
5
v
7
v
7
v
6
v
5
v
2
v
3
v
4
v
1
14
图的染色是内容十分丰富而又应用广泛的一个图论专题。 关于染色问题可进一步参考文献 [116]~[91]。其 中 [116]~[118]是与图染色问题有关的专著,[119]~[120]是与图染色有关的网页,[121]~[122]讨论图的边染色,[123]~[125] 研究有约束的图染色问题,[126]~[127]研究赋权染色问题,[128]~[129]涉及图的色幂（ coloring powers）,[130]~[134]与随机图染色和随机算法有关,[135]~[138]研究全染色和全色数（ total-coloring）,[139]~[142]研究表色数
（ list-coloring）,[143]~[150]涉及图的和染色（ sum coloring）及相关算法的性能,[151]~[167]
研究其他与图的染色有关的问题,[168]~[171]研究染色问题在寄存器配置中的应用，
[172]~[180]是有关染色问题在通信网络优化、地理信息系统等方面的应用。
[116] Reinhard Diestel,Graph Theory,Springer,1997,
[117] Tommy R,Jensen and Bjarne Toft,Graph Coloring Problems,Wiley-Interscience,New
York,1995,
[118] B,Toft,75 graph-colouring problems,in Graph Colourings (R,Nelson and R.J,Wilson,
Eds.),Wiley,New York,(1990),pp9-35,
[119] http://www.nada.kth.se/~viggo/problemlist/
[120] http://web.cs.ualberta.ca/~joe/Coloring/#Links.other
[121] L.D,Andersen,On edge-colourings of graphs,Math,Scand,40(1977),pp161-175,
[122] N,Rorbertson,P,D,Seymour and R,Thomas,Tutte’s edge-coloring conjecture,J,Combin,
Theory (Ser,B),70(1997),pp166-183,
[123] N,Alon,Restricted colorings of graphs,in Surveys in Combinatorics 1993 (Proc,14
th
British Combinatorial Conference),Cambridge Univ,Press,Cambridge,(1993),pp1-33,
[124] H.R,Hind,Restricted Edge-Colourings,Ph.D,thesis,University of Cambridge,1988,
[125] M,Caramia and P,Dell'Olmo,Constraint propagation in graph coloring,Journal of
Heuristics,8(1) (2002),pp83-107,
[126] Egon Balas and Jue Xue,Minimum weighted coloring of triangulated graphs,with
application to maximum weight vertex packing and clique finding in arbitrary graphs,SIAM
Journal on Computing,20(2) (1991),pp209-221,
[127] M,Caramia and P,Dell'Olmo,Solving the minimum-weighted coloring problem,Networks,
38(2) (2001),pp88-101,
[128] D,Král',Coloring Powers of Chordal Graphs,SIAM J,Discrete Math.,18(2004-2005),
pp451-461,
[129] G,Agnarsson and M,M,Halldórsson,Coloring Powers of Planar Graphs,SIAM J,Discrete
Math.,16(2002-2003),pp651-662,
[130] R.Motwani and P,Raghavan,Randomized Algorithms,Cambridge University Press,New
York,1995,
[131] U,Feige,Randomized graph products,chromatic numbers,and the Lovász?-function,in
Proceedings of the 27
th
Annual ACM Symposium on Theory of Computing,(1995),635-640,
[132] T,Luczak,The chromatic number of random graphs,Combinatorica,11(1) (1991),
pp45-54,
[133] M,Fürer and C,R,Subramanian,Coloring random graphs,In Proceedings 3rd
15
Scandinavian Workshop on Algorithmic Theory,Berlin,1992,Springer Lecture Notes in
Computer Science,
[134] Cécile Murat,Vangelis Th,Paschos,On the probabilistic minimum coloring and minimum
k-coloring,Discrete Applied Mathematics,154(2006),pp564-586,
[135] V,A,Bojarshinov,Edge and total coloring of interval graphs,Discrete Applied Mathematics,
114(2001),pp23-28,
[136] O.V,Borodin,On the total coloring of planar graphs,J,Reine Angew,Math.,394(1989),
pp180-185,
[137] D.L,Chen and J,L,Wu,The total coloring of some graphs,in,Combinatorics,Graph
Theory,Algorithms,and Applications,Beijing,1993”,World Science,River Edge,NY,(1994),
pp17-20,
[138] Celina M.H,de Figueiredo,J,Meidanis,and C,P,De Mello,Total-Chromatic number and
chromatic index of dually chordal graphs,Information Processing Letters,70(1999),pp147-152,
[139] A,Daneshgar and H,Hajiabolhassan,Unique list-colourability and the fixing chromatic
number of graphs,Discrete Applied Mathematics,152(2005),pp123-138
[140] O.V,Borodin and A.V,Kostochka,List edge and list total colorings of multigraphs,Journal
of Combinatorial Theory (Ser,B),71(1997),pp184-204,
[141] F,Galvin,The list chromatic index of a bipartite multigraph,Journal of Combinatorial
Theory (Ser,B),63(1995),pp153-158,
[142] J,Kahn,Asymptotically good list-colorings,J,Combin,Theory (Ser,A),73(1996),pp1-59,
[143] M,R,Salavatipour,On sum coloring of graphs,Discrete Applied Mathematics,127(2003),
pp477-488,
[144] Bar-Noy,A.,Bellare,M.,Halldórsson,M,M.,Shachnai,H.,and Tamir,T,(1998),On
chromatic sums and distributed resource allocation,Inform,and Comput,140,183-202,
[145] Bar-Noy,A.,Halldórsson,M,M.,Kortsarz,G.,Shachnai,H.,and Salman,R,(1999),Sum
multicoloring of graphs,Proc,7th Ann,European Symp,on Algorithms,Lecture Notes in Comput,
Sci.,Springer-Verlag,
[146] Bar-Noy,A.,and Kortsarz,G,(1998),The minimum color sum of bipartite graphs,J,
Algorithms 28,339-365,
[147] Halldórsson,M,M.,and Kortsarz,G,(1999),Multicoloring planar graphs and partial k-trees,
Proc,2nd Int,Workshop on Approximation Algorithms for Combinatorial Problems,Lecture
Notes in Comput,Sci.,Springer-Verlag,
[148] Halldórsson,M,M.,Kortsarz,G.,Proskurowski,A.,Salman,R.,Shachnai,H.,and Telle,J,
A,Multi-coloring trees,Proc,5th Ann,Int,Conf,on Computing and Combinatorics,Lecture
Notes in Comput,Sci.,Springer-Verlag,(1999),271-280,
[149] Jansen,K,(2000),Approximation results for the optimum cost chromatic partition problem,
J,Algorithms 34,54-89,
[150] S,Nicoloso,X,Song,M,Sarrafzadeh (1999),On the sum coloring problem on interval
graphs,Algorithmica 23,109-126,
[151] H,Enomoto,M,Hornák,and S,Jendrol',Cyclic chromatic number of 3-connected plane
graphs,SIAM J,Discrete Math.,14(2001),pp121-137,
16
[152] Oleg V,Borodin and Douglas R,Woodall,Cyclic colorings of 3-polytopes with large
maximum face size,SIAM J,Discrete Math.,15(2001-2002),pp143-154,
[153] M,Larsen,J,Propp,and D,Ullman,The fractional chromatic number of Mycielski’s graphs,
J,Graph,Theory,19(1995),pp411-416,
[154] G,Chartrand,L,Nebesky and P,Zhang,Hamiltonian colorings of graphs,Discrete Applied
Mathematics,146(2005),pp257-272
[155] M,O,Albertson,A,V,Kostochka,and D,B,West,Precoloring Extensions of Brooks'
Theorem,SIAM J,Discrete Math.,18(2004-2005),pp542-553,
[156] J,Janssen and K,Kilakos,Bounded Stable Sets,Polytopes and Colorings,SIAM J,Discrete
Math.,12(1999),pp262-275,
[157] G,Bacsó,S,Gravier,A,Gyárfás,M.,Preissmann,and A,Sebo,Coloring the Maximal
Cliques of Graphs,SIAM J,Discrete Math.,17(2003-2004),pp361-376,
[158] Chaudhary,A.,and Vishwanathan,S,(1997),Approximation algorithms for the achromatic
number,Proc,8th Ann,ACM-SIAM Symp,on Discrete Algorithms,ACM-SIAM,558-563,
[159] V,Guruswami and S,Khanna,On the Hardness of 4-Coloring a 3-Colorable Graph,SIAM J,
Discrete Math.,18(2004-2005),pp30-40,
[160] A,Gyárfás,Z,Király,and J,Lehel,On-Line 3-Chromatic Graphs I,Triangle-Free Graphs,
SIAM J,Discrete Math.,12(1999),pp385-411,
[161] N,Alon and M,Krivelevich,Testing k-colorability,SIAM J,Discrete Math.,15(2001-2002),
pp211-227,
[162] A,Hertz,B,Jaumard,and M,P,de Aragao,Local optima topology for the k-coloring
problem,Discrete Applied Mathematics,49(1-3) (1994),pp257-280,
[163] J,Fiala,K,Jansen,V,B,Le,and E,Seidel,Graph Subcolorings,Complexity and
Algorithms,SIAM J,Discrete Math.,16(2002-2003),pp635-650,
[164] U,Feige,M,Langberg,and G,Schechtman,Graphs with Tiny Vector Chromatic Numbers
and Huge Chromatic Numbers,SIAM J,Computing,33(2003-2004),pp1338-1368
[165] M,Vasquez,New results on the queens_n
2
graph coloring problem,Journal of Heuristics,
10(4) (2004),pp407-413,
[166] J,Culberson and I,P,Gent,Frozen development in graph coloring,Theoretical Computer
Science,265(1-2) (2001),
[167] A.V,Gelder,Another look at graph coloring via propositional satisfiability,(2002),48-54,
Ithaca,New York,USA,
[168] G,Chaitin,Register allocation and spilling via graph coloring,SIGPLAN Not.,39(4) (2004),
pp66-74,
[169] Fred C,Chow and John L,Hennessy,The priority-based coloring approach to register
allocation,ACM Transactions on Programming Languages and Systems,12(4) (1990),pp501-536,
[170] Allen M.,Kumaran G.,and Liu T,(2002),A combined algorithm for graph-coloring in
register allocation,pp,100-111,Ithaca,New York,USA,
[171] M.D,Smith,N,Ramsey,and G,Holloway,A generalized algorithm for graph-coloring
register allocation,In PLDI '04,Proceedings of the ACM SIGPLAN 2004 Conference on
Programming Language Design and Implementation,(2004),pp277-288,ACM Press,New York,
NY,USA,
17
[172] S,Gerke,Weighted colouring and channel assignment,DPhil thesis,University of Oxford,
2000,
[173] C,Mcdiarmid,and B,Reed,Channel assignment and weighted colouring,Networks,
36(2000),pp114-117,
[174] A,Zymolka,A.M.C.A,Koster,and R,Wess?ly,Transparent optical network design with
sparse wavelength conversion,In Proceedings of the 7th IFIP Working Conference on Optical
Network Design & Modelling,(2003),pp 61-80,Budapest,Hungary,
[175] C,Nomikos,A,Pagourtzis and S,Zachos,Routing and path multicoloring,Information
Processing Letters,80(2001),pp249-256,
[176] Hung Q,Ngo and Van H,Vu,Multirate Rearrangeable Clos Networks and a Generalized
Edge-Coloring Problem on Bipartite Graphs,SIAM J,Computing,32(2002-2003),pp1040-1049,
[177] Andreas Gamst,Some lower bounds for a class of frequency assignment problems,IEEE
Transactions of Vehicular Echnology,35(1) (1986),pp8-14,
[178] M,R,Garey,D,S,Johnson,and H,C,So,An application of graph coloring to printed
circuit testing,IEEE Trans,on Circuits and Systems,CAS-23 (1976),pp591-599,
[179] N,Barnier and P,Brisset,Graph coloring for air traffic flow management,In CPAIOR'02,
Fourth International Workshop on Integration of AI and OR Techniques in Constraint
Programming for Combinatorial Optimisation Problems,(2002),pp133-147,Le Croisic,France,
[180] R,Freimer,Generalized map coloring for use in geographical information systems,In
ACM-GIS 2000,Proceedings of the Eighth ACM Symposium on Advances in Geographic
Information Systems,edited by K.J,Li,K,Makki,N,Pissinou,and S,Ravada,(2000),pp167-173,
ACM press,New York,NY,USA,
§ 6.5 染色应用举例—求图的边色数及色数的算法
一、排课表问题—求二部图的正常 )(Gχ′ 边染色
1,问题,有 m 位教师
m
xxx,,,
21
null,n 个班级
n
yyy,,,
21
null 。教师 x
i
每周需要给班级 y
j
上
p
ij
次（节）课。要求制订一张周课时尽可能少的课程表。
2,图论模型,构造二部图 ),( YXG =,其中 X＝ {
m
xxx,,,
21
null },Y＝ {
n
yyy,,,
21
null }，
顶点
i
x 与
j
y 之间连
ij
p 条边。
一个课时的安排方案对应于二部图 G 的一个匹配。排课表问题等价于：将 E(G)划分成一些匹配，使得匹配的数目尽可能地少。
按 )(Gχ′ 的定义，这个最小的数目便是 )(Gχ′ 。由定理 6.2.1,() ()GGχ′ =Δ 。因此，
排课表问题等价于：求二部图 G 的边正常 )(GΔ 染色。
如§ 6.1 中所述，虽然求简单图的正常（ 1+Δ ）边染色存在多项式时间算法，但求简单图 G 的边色数 )(Gχ′ 及其相应的正常边染色是一个 NPC 问题
[28]
。尽管如此，求二部图的边正常 Δ 染色却有多项式时间算法。求图的边色数的近似算法可参考文献 [29]~[51]。
[28] I,Holyer,The NP-completeness of edge-coloring,SIAM J,Computing,10,4(1981),718-720,
[29] E,Petrank,The hardness of approximation,gap location,Computational Complexity,4
(1994),133-157,
[30] D,Leven and Z,Galil,NP completeness of finding the chromatic index of regular graphs,J,
Algorithms,4(1983) 35-44,
[31] P,Crescenzi,V,Kann,R,Silvestri,and L,Trevisan,Structure in approximation classes,SIAM
J,Comp.,28 (1999),1759-1782,
[32] J,Misra and D,Gries,A constructive proof of Vizing's theorem,Inform,Process,Lett,41
(1992),131-133,
[33] O,Terada,and T,Nishizeki,Approximate algorithms for the edge-coloring of graphs,Trans,
Inst,Eletron,Commun,Engr,Japan J65-D,11(1982),1382-1389,
[34] M,Chrobak,and T,Nishizeki,Improved edge-coloring algorithms for planar graphs,J,
Algorithms,11(1990),102-116,
[35] I,Caragiannis,A,Ferreira,C,Kaklamanis,S,Perennes,P,Persiano and H,Rivano,
Approximate constrained bipartite edge coloring,Discrete Applied Mathematics,143(2004),54-61
[36] M,R,Salavatipour,A polynomial time algorithm for strong edge coloring of partial k-trees,
Discrete Applied Mathematics,143(2004),285-291,
[37] D.A,Grable,A,Panconesi,Nearly optimal distributed edge coloring in O (log log n) rounds,
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms,January,
(1997),278–285,
[38] Yijie Han,Weifa Liang and Xiaojun Shen,Very fast parallel algorithms for approximate edge
coloring,Discrete Applied Mathematics,108(2001),227-238,
[39] M,Fürer and B,Raghavachari,Parallel edge coloring approximation,Parallel Process,Lett.,
6 (1996),321–329,
2
[40] H.J,Karloff and D.B,Shmoys,Efficient parallel algorithms for edge coloring problems,J,
Algorithms 8 (1987),39–52,
[41] W,Liang,Fast parallel algorithms for the approximate edge-coloring problem,Inform,
Process,Lett,56 (1995),333–338,
[42] W,Liang,X,Shen and Q,Hu,Parallel algorithms for the edge-coloring and edge-coloring
update problems,J,Parallel Distrib,Comput,32 (1996),66-73,
[43] R,Motwani,J,Naor and M,Naor,The probabilistic method yields deterministic parallel
algorithms,J,Comput,System Sci,49 (1994),478-516,
[44] D,Bertsimas,C-P,Teo,and R,Vohra,On dependent randomized rounding algorithms,Proc,
5th Int,Conf,on Integer Prog,and Combinatorial Optimization,Lecture Notes in Comput,Sci,
1084,Springer-Verlag,(1996),330-344,
[45] M.K,Goldberg,Edge-colorings of multigraphs,recoloring technique,J,Graph Theory,
8(1984),123-127,
[46] D.S,Hochbaum,T,Nishizeki and D.B,Shmoys,Better than,Best Possible” algorithm to
edge color multi graphs,Journal of Algorithms,7(1986),79-104
[47] T,Nishizeki and K,Kashiwagi,On the 1.1 edge-coloring of multigraphs,SIAM J,Disc,
Math.,3(1990),391-410,
[48] J,Kahn,Asymptotics of the chromatic index for multigraphs,Journal of Combinatorial
Theory (Ser,B),68(1996),233-254,
[49] X,Zhou H,Susuki,and T,Nishizeki,A linear algorithm for edge-coloring series-parallel
multigraphs,J,Algorithms,20(1996),174-201,
[50] X,Zhou H,Susuki,and T,Nishizeki,An NC parallel algorithm for edge-coloring
series-parallel multigraphs,J,Algorithms,23(1997),359-374,
[51] B,Berger and J,Rompel,Simulating (log
c
n)-wise independence in NC,J,ACM 38 (1991),
1026–1046,
3,求二部图 ),( YXG = 的边正常 )(GΔ 染色的算法
z 算法思想,给 G 添加必要的顶点使得 |||| YX =,再添加必要的边使得 G 成为 )(GΔ 正则二部图,所得图记为
*
G,然后反复运用匈牙利算法求
*
G 的完美匹配。 由第 3 章 K?nig
定理，
*
G 存在完美匹配。每求出
*
G 的一个完美匹配，便可用一种颜色给这个完美匹配的边染色。因为共可求得
*
G 的 )(GΔ 个边不重的完美匹配，故可得
*
G （从而 G）的边正常 )(GΔ 染色。
z 二部图边染色算法,求二部图的边正常 )(GΔ 染色 (求二部图的 )(GΔ 个边不交的匹配 )。
输入：二部图 G=(X,Y)
输出,G 的边正常 )(GΔ 染色（ )(GΔ 个边不交的匹配）
第 0 步：添加顶点使得 |X|=|Y|，所得图记为
*
G 。
第 1 步：若 )()(
**
GG δ=Δ,令 1=k,转第 3 步；否则，转第 2 步。
3
第 2 步：取 Xx ∈
0
,Yy ∈
0
，使得 )(min)(
**
0 i
G
Xx
G
xdxd
i
∈
=,)(min)(
**
0 i
G
Yy
G
ydyd
i
∈
=,令
00
**
,yxGG +=,转第 1 步。
第 3 步：任取
*
G 的一个匹配 M。
第 4 步：若 X 已 M 饱和，则输出当前的完美匹配，转第 7 步；否则取 X 中一个 M 不饱和点 u，置 }{,uS =,φ=:T 。
第 5 步：在 TSN \)( 中取一点 y,
第 6 步：若 y 是 M 饱和的，则存在 Myz∈,置 }{,zSS ∪=,}{,yTT ∪=,转第 5 步；
否则，存在一条 M 可扩路 P ),( yu,置 )(,PEMM ⊕=,转第 4 步。
第 7 步：若 Δ=k,则停止；否则，令 1,+= kk,MGG \:
**
=,转第 3 步。
设 ||||X Y≥ 。因匈牙利算法的时间复杂性为
3
(| | )OX,而第 1 步和第 2 步的加边循环不超过 Δ?|| X 次，故该算法是多项式时间算法。
4,带有约束的排课表问题
设学校每周有 l 节课，安排在一张有 p 节课时的课表中（前面的方法求得一个 Δ 节课时的课表） 。这样，平均每一课时要上
p
l
节课，因此需要
p
l
间教室。比如,510=l,
20=p,则需要 26
20
510
=
=
p
l
间教室。
问题,可否在一张有 p 节课时的课表里安排 l 节课,使得在一节课时内至多用
p
l
间教室？
下面的引理见第 3 章习题。
引理 6.5.1 设 M 和 N 是图 G 的两个无公共边的匹配，并且 |||| NM >,则存在 G 的无公共边的匹配 M′和 N′，使得 1||||?=′ MM,1|||| +=′ NN,且 NMNM ∪∪ =′′ 。
定理 6.5.1 若图 G 是一个二部图，且 ()p G≥Δ,则 G 中存在 p 个无公共边的匹配
p
MMM null,,
21
，使得
p
MMME ∪null∪∪
21
=,且对每个 ),,2,1( pii null= 均有
≤≤
p
G
M
p
G
i
)(
||
)( εε
。
证明,因图 G是二部图,故由本章定理 6.1.1,边集 )(GE 可划分为 Δ 个匹配
Δ
′′′ MMM,,,
21
null,
因而对任何 )(Gp Δ≥,G 中存在 p 个无公共边的匹配,,,,
21 Δ
′′′ MMM null
p
MM ′′
+Δ
,,
1
null （其中 φ=′==′
+Δ p
MM null
1
）,使得
∪
p
i
i
MGE
1
)(
=
′= 。对这些匹配反复运用引理 6.5.1，便可得到满足定理要求的匹配。证毕。
这个定理对前述带约束排课表问题给出了肯定回答。 同时也给出了求所需教室数最少的
p 课时课表的方法：先按二部图边染色算法求出相应二部图的一个正常 )(GΔ 边染色，然后
4
反复运用引理 6.5.1 对其进行调整，最终使得染不同颜色的两个边集所含边数至多相差 1。
例 6.5.1 设有 4 个教师 x
1
,x
2
,x
3
,x
4
和 5 个班级 y
1
,y
2
,y
3
,y
4
,y
5
，教学矩阵 )(
ij
tT = 表示如下,
=
11000
01110
01010
01102
4
3
2
1
54321
x
x
x
x
yyyyy
T
问,（ 1）课表至少需要几课时？
（ 2）按二部图边染色算法给出一个课时数最少的课表。
（ 3）在课时数最少的前提下，给出需教室数最少的课表方案。
解：构造二部图如下图 1,
图 1 图 2
由于 4)( =Δ G,故课表至少需 4 课时。
执行二部图边染色算法得 G 的 4 个边不交的匹配 (如图 2)。 相应的一个 4 课时课表如下,
教师 课时
1 2 3 4
x
1
y
1
y
1
y
3
y
4
x
2
y
2
y
4
x
3
y
3
y
4
y
2
x
4
y
4
y
5
按这张课表安排，需 4 个教室。但因 11)( =Gε,3
4
11
=
=
p
ε
，由定理 6.4.1，可排出一张只需 3 个教室的 4 课时课表。事实上，将教师
4
x 在第 1 课时的课调到第 3 课时而将教师
2
x 在第 3 课时的课与第 1 课时对调即可。从二部图的匹配上来看，是将第 1 课时和第 3 课时对应的匹配施行了一次引理 6.4.1 的操作。一张只需 3 个教室的 4 课时课表如下,
教师 课时
1 2 3 4
x
1
y
1
y
1
y
3
y
4
x
2
y
4
y
2
x
3
y
3
y
4
y
2
x
4
y
5
y
4
x
4
x
3
x
2
x
1
y
1
y
2
y
3
y
4
y
5
x
4
x
3
x
2
x
1
y
1
y
2
y
3
y
4
y
5
5
二、点染色的应用及正常 )(Gχ 点染色的求法
1．应用背景举例
（ 1）考试安排问题
某校有 n 门选修课
n
LLL,,,
21
null 需进行期末考试,同一个学生不能在同一天里参加两门或两门以上课程的考试。试问：该校的期末考试至少需要几天？如何安排？
图论模型：构造图 G＝ (V,E)如下,=)(GV {
n
LLL,,,
21
null },)(GELL
ji
∈ 当且仅当课程
i
L 和
j
L 被同一学生选修。
将同一天的考试课程在 G 中对应的顶点染同一种色，则考试安排相当于对 G 进行顶点正常染色。所求最少天数即为 G 的点色数 )(Gχ 。问题化为：求图 G 的正常 )(Gχ 点染色。
（ 2）电视频道分配问题
某地区有 n 家电视发射台
n
TTT,,,
21
null,主管部门给每家电视台分配一个发射频道。为排除同频干扰，使用相同频道的发射台之间相距必须大于一定的距离 d。试问：该地区至少需要多少个频道？如何分配？
图论模型：构造图 G＝ (V,E)如下,=)(GV {
n
TTT,,,
21
null },)(GETT
ji
∈ 当且仅当发射台
i
T 和
j
T 的距离不超过 d。
考虑 G 图的正常点染色。易见染同一种色的顶点可分配给同一频道。反之，按要求分配一个频道，相当于给 G 中相应的顶点染同一种色。因此，频道分配相当于对 G 进行顶点正常染色。所求最少频道数即为点色数 )(Gχ 。问题化为：求图 G 的正常 )(Gχ 点染色。
（ 3）储藏问题
某公司生产 n 种化学品
n
CCC,,,
21
null,其中某些制品不能存放在同一个仓库中。问至少需要多少个仓库？如何分配存放？
图论模型：构造图 G＝ (V,E)如下,=)(GV {
n
CCC,,,
21
null },)(GECC
ji
∈ 当且仅当制品
i
C 和
j
C 不能放在同一仓库中。
若干制品可放在同一仓库当且仅当它们在 G 中对应的顶点可染同一种色。可见给这些产品分配仓库相当于对 G 进行正常点染色。所需的最少仓库数即为 G 的点色数 )(Gχ 。问题化为：求图 G 的正常 )(Gχ 点染色。
对既不是完全图又不是奇圈的图 G,利用 Brooks定理的证明可以得到求 G的顶点 (G)Δ -
正常染色的一个有效算法
[116]
。但是，在一般情况下,(G)Δ 与 )(Gχ 并不相等。求任意图的正常 )(Gχ 点染色是一个 NPC 问题
[116]
，目前没有多项式时间精确算法，仅有一些适用于小规模问题的非多项式时间算法和一些多项式时间近似算法。遗憾的是，迄今为止找到的多项式时间近似算法其近似比都不等于常数。可见，从计算复杂性的角度来看，图的点染色问题是如此困难，以至于连近似比等于常数的多项式时间近似算法都难以找到。实际上，已经证
6
明，如果存在多项式时间染色算法使得对每个图 G 都可使用不多于 2(G)χ 种色进行正常顶点染色，则必定存在 G 的 (G)χ 顶点染色有效算法
[117][118]
。这表明，对图的点染色问题，找近似比等于常数的多项式时间近似算法与找 (G)χ 顶点染色的（有效）精确算法一样困难。
下面介绍点染色问题的几种非多项式时间算法和简单的近似算法。 更多的算法可参见文献 [52]~[115]，其中 [52]~[58]是与图的点染色算法有关的专著,[59]~[72]研究图的点染色问题的各种精确算法,[73]~[89]研究图的点染色问题的近似算法及其性能，在不同条件下给出了较低近似比的染色算法,[90]~[111]将邻域方法、禁忌搜索和局部搜索方法、模拟退火法、
人工神经网络、遗传算法、蚁群算法等方法以及其它一些启发式方法用于图的点染色问题。
[112]-[115]讨论点染色的相关计算复杂性问题。
[52] G,Chartrand,O,R,Oellermann,Applied and Algorithmic Graph Theory,McGraw-Hill,Inc.,
New York,(1993),283-310,
[53] M.R,Garey and D.S,Johnson,Computers and Intractibility,A Guide to the Theory of
NP-Completeness,Freeman,New York,1979,
[54] D.S,Hochbaum,Approximation Algorithms for NP-hard Problems,International Thomson
Publishing Inc.,1997 (影印本,NP 难解问题的近似算法，世界图书出版公司 )。
[55] N,Christofides,Graph Theory,An Algorithmic Approach,Academic Press,New York,
(1990),58-78,
[56] S,Even,Algorithmic Combinatorics,Macmillan,New York,1973,
[57] R,Gould,Graph Theory,Benjamin Cummings,Menlo,Park,CA(1988),
[58] D.W,Matula,G,Marble,and J.D,Isaacson,Graph colouring algorithms,in Graph Theory
and Computing (Read Ed.),Academic Press,New York,(1972) 109-122,
[59] D,Brelaz,New methods to color the vertices of a graph,Communications of the Association
for Computing Machinery,22(1979),251-256,
[60] E.C.Sewell,An Improved algorithm for exact graph coloring,in,Cliques,Coloring and
Satisfiability”,(DIMACS Series in Discrete Mathematics and Theoretical Computer Science),
26 (1996),359-373,American Mathematical Society,Providence,RI,USA,
[61] D,Eppstein,Small maximal independent sets and faster exact graph coloring,Journal of
Graph Algorithms and Applications,7(2) (2003),131-140,
[62] N,Christofides,An algorithm for the chromatic number of a graph,The Computer Journal,
14(1971),38-39,
[63] D,G,Corneil and B,Graham,An algorithm for determining the chromatic number of a graph,
SIAM Journal on Computing,2(1973),211-218,
[64] D,Kirovski and M,Potkonjak,Efficient coloring of a large spectrum of graphs,In DAC '98,
Proceedings of the 35th annual conference on Design automation,(1998),427-432,ACM Press,
New York,NY,USA,
[65] Ojvind Johansson,Simple distributed 1Δ+ -coloring of graphs,Information Processing
Letters,70(1999),229-232,
[66] I.M,Diaz and P,Zabala,A branch-and-cut algorithm for graph coloring,(2002),55-62,Ithaca,
New York,USA,
7
[67] M,Caramia and P,Dell'Olmo,Bounding vertex coloring by truncated multistage branch and
bound,Networks,44(4) (2004),231-242,
[68] M,Kubale and B,Jackowski,A generalized implicit enumeration algorithm for graph
coloring,Communications of the ACM,28 (1985),412-418,
[69] A,Mehrotra and M,Trick,A column generation approach for graph coloring,INFORMS
Journal On Computing,8(4) (1996),344-354,
[70] S.R,Vegdahl,Using node merging to enhance graph coloring,In PLDI '99,Proceedings of
the ACM SIGPLAN 1999 conference on Programming language design and implementation,
(1999),150-154,ACM Press,New York,NY,USA,
[71] F,Herrmann and A,Hertz,Finding the chromatic number by means of critical graphs,
Journal of Experimental Algorithmics,7(2002),p10,
[72] G.A,Kochenberger,F,Glover,B,Alidaee,and C,Rego,An unconstrained quadratic binary
approach to the vertex coloring problem,Annals of Operations Research,139(1) (2005),229-241,
[73] A,Wigderaon,improving the performance guarantee for approximate graph coloring,Journal
of the ACM,30(1983),729-735,
[74] B,Berger and J,Rompel,A better permance guarantee for approximate graph coloring,
Algorithmica,5(1990),459-466,
[75] M,M,Halldórsson,A still better performance guarantee for approximate graph coloring,
Information Processing Letters,45(1993),19-23,
[76] M,Bellare,O,Goldreich,and M,Sudan,Free bits,PCPs and non-approximability - towards
tight results,SIAM J,Comp,27(1998),804-915,
[77] A,Blum,and D,Karger,An
3
14
()On
null
-coloring algorithm for 3-colorable graphs,Information
Processing Letters,61(1997),49-53,
[78] L,J,Cowen,W,Goddard,and C,E,Jesurum,Coloring with defect,Proc,8th Ann,
ACM-SIAM Symp,on Discrete Algorithms,ACM-SIAM,(1997),548-557,
[79] R,Duh,and M,Fürer,Approximation of k-set cover by semi-local optimization,Proc,29th
Ann,ACM Symp,on Theory of Comp.,ACM,(1997),256-265,
[80] D,Karger,R,Motwani,and M,Sudan,Approximate graph coloring by semidefinite
programming,J,ACM,45(1998),246-265,或见 Proceedings of the 35
th
Annual IEEE
Symposium on Foundations of Computer Science,(1994),2-13,
[81] M,Krivelevich,and B,Sudakov,Approximate coloring of uniform hypergraphs,Proc,6th
Ann,European Symp,on Algorithms,Lecture Notes in Comput,Sci.,Springer-Verlag,(1998),
477-489,
[82] T,Hofmeister,and H,Lefmann,Approximating maximum independent sets in uniform
hypergraphs,Proc,23rd International Symp,on Mathematical Foundations of Comput,Sci.,
Lecture Notes in Comput,Sci,1450,Springer-Verlag,(1998),562-570,
[83] U,Feige,and J,Kilian,Zero knowledge and the chromatic number,Journal of Computer and
System Sciences,57(2)(1998),187-199,
[84] V,Kumar,Approximating circular arc colouring and bandwidth allocation in all-optical ring
networks,Proc,1st Int,Workshop on Approximation Algorithms for Combinatorial Problems,
Lecture Notes in Comput,Sci.,Springer-Verlag,(1998),147-158,
8
[85] S,Khanna,N.Linial,and S,Safra,On the hardness of approximating the chromatic number,
Proc,2nd Israel Symp,on Theory of Computing and Systems,IEEE Computer Society,(1993),
250-260,
[86] C,Lund,and M,Yannakakis,On the hardness of approximating minimization problems,J,
ACM 41(1994),960-981,
[87] M,V,Marathe,H,Breu,H,B,Hunt III,S,S,Ravi,and D,J,Rosenkrantz,Simple heuristics
for unit disk graphs,Networks,25(1995),59-68,
[88] A,Blum,New Appproximation algorithms for graph coloring,Journal of the ACM,41(1994),
470-516,
[89] A,Blum,Some tools for approximate 3-coloring,In Proceedings 31st IEEE Symposium on
Foundations of Computer Science,pages 554-562,Los Angeles,CA,1990,IEEE Computer
Society,
[90] M,Laguna and R,Martí,A GRASP for coloring sparse graphs,Computational optimization
and applications,19(2) (2001),165-178,
[91] Alon N.,Krivelevich M.,and Sudakov B.,Coloring graphs with sparse neighborhoods,
Journal of Combinatorial Theory,Ser,B,77(1999),73-82,
[92] Morgenstern C,and Shapiro H.,Coloration neighborhood structures for general graph
coloring,In Proceedings of the first annual ACM-SIAM Symposium on Discrete algorithms,
(1990),226-235,Society for Industrial and Applied Mathematics,Philadelphia,PA,USA,
[93] Avanthay C.,Hertz A.,and Zufferey N.,A variable neighborhood search for graph coloring,
European Journal of Operational Research,(2003),
[94] Glass C.A,and Prügel-Bennett A.,A polynomially searchable exponential neighbourhood for
graph colouring,Journal of the Operational Research Society,56(3) (2005),pp,324-330,
[95] Hertz A,and de Werra D.,Using tabu search techniques for graph coloring,Computing,39(4)
(1987),345-351,
[96] González-Velarde J,and Laguna M.,Tabu search with simple ejection chains for coloring
graphs,Annals of Operations Research,117(1-4) (2002),165-174,
[97] Chiarandini M,and Stützle T.,An application of iterated local search to graph coloring,In
Proceedings of the Computational Symposium on Graph Coloring and its Generalizations,edited
by D.S,Johnson,A,Mehrotra,and M,Trick,(2002),112-125,Ithaca,New York,USA,
[98] Fleurent C,and Ferland J.,Object-oriented implementation of heuristics search methods for
graph coloring,maximum clique,and satisfiability,vol,26 of DIMACS Series in Discrete
Mathematics and Theoretical Computer Science,(1996),619-652,American Mathematical
Society,Providence,RI,USA,
[99] D,de Werra,Lausanne,Heuristics for graph coloring,Computing Supplementum,7(1990)
191-208,
[100] Blas A.D.,Jagota A.,and Hughey R.,A range-compaction heuristic for graph coloring,
Journal of Heuristics,9(3) (2003),489-506,
[101] Lewandowski G,and Condon A.,Experiments with parallel graph coloring heuristics and
applications of graph coloring,vol,26 of DIMACS Series in Discrete Mathematics and
Theoretical Computer Science,(1996),309-334,American Mathematical Society,Providence,RI,
USA,
9
[102] Fabrikant A,and Hogg T.,Graph coloring with quantum heuristics,In Proceedings of the
Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on
Innovative Applications of Artificial Intelligence,Edmonton,Alberta,Canada,AAAI Press,(2002),
22-27,
[103] David S,Johnson,Cecilia R,Aragon,Lyle A,McGeoch,and Catherine Schevon,
Optimization by simulated annealing,An experimental evaluation; part II,graph coloring and
number partitioning,Operations Research,39(3):378-406,1991,
[104] Jagota A.,An adaptive,multiple restarts neural network algorithm for graph coloring,
European Journal of Operational Research,93(2) (1996),257-270,
[105] Cutello V.,Nicosia G.,and Pavone M.,A hybrid immune algorithm with information gain
for the graph coloring problem,vol,2723 of Lecture Notes in Computer Science,(2003),
171-182,Springer Verlag,Berlin,Germany,
[106] Glass C.A,and Prügel-Bennett A.,Genetic algorithms for graph colouring,Exploration of
Galinier and Hao's algorithm,Journal of Combinatorial Optimization,7(3) (2003),229-236,
[107] Croitoru C.,Luchian H.,Gheorghies O.,and Apetrei A.,A new genetic graph coloring
heuristic,(2002),63-74,Ithaca,New York,USA,
[108] Galinier P,and Hao J.,Hybrid evolutionary algorithms for graph coloring,Journal of
Combinatorial Optimization,3(4) (1999),379-397,
[109] Eiben A.E.,Hauw J.K.V.D.,and Hemert J.I.V.,Graph coloring with adaptive evolutionary
algorithms,Journal of Heuristics,4(1) (1998),pp,25-46,
[110] Bui T.N,and Patel C.M.,An ant system algorithm for coloring graphs,(2002),83-91,Ithaca,
New York,USA,
[111] D,C,and Hertz A.,Ants can colour graphs,Journal of the Operational Research Society,
48(1997),295-305,
[112] Paschos V.T.,Polynomial approximation and graph-coloring,Computing,70(1) (2003),
41-86,
[113] J,S,Turner,Almost all -colorable graphs are easy to color,Journal of Algorithms,9(1988),
63-82,
[114] Ludek Kucera,Graphs with small chromatic numbers are easy to color,Information
Processing Letters,30(1989),233-236,
[115] Ludek Kucera,The greedy coloring is a bad probabilistic algorithm,Journal of Algorithms,
12(1991),674-684,
2,求图 G 的色数 )(Gχ 及正常 )(Gχ 点染色的算法
z 添边粘合法
添边、粘合操作：给定图 G＝ (V,E)，设 )(,GVvu ∈,且 u,v 在 G 中互不相邻，则
（ 1） 添边操作,给 G 添加边 uv，得图 G′；
（ 2） 粘合操作,将 u,v 两点粘合为一点，并去掉所得的重边，得图 G′′ 。
10
例如,
定理 6.4.2 )}(),(min{)( GGG ′′′= χχχ 。
证明：考虑图 G 的所有可能的正常点染色方案。设 u,v 是 G 中互不相邻的两点，则在 G 中的正常染色下 u,v 的染色有两种可能,u 与 v 同色，或 u 与 v 异色。 G 的使 u 与 v 染同色的正常点染色方案与 G′′ 的正常点染色方案一一对应,而 G 的使 u 与 v 染异色的正常点染色方案与 G′的正常点染色方案一一对应。因此 )}(),(min{)( GGG ′′′= χχχ 。证毕。
添边粘合算法基本思想,对于给定的图 G，若 G 是一个 υ阶完全图，则 ()Gχ υ= 。此时给
G 的每个顶点一个不同的色即可。若 G 不是完全图，则可取两个不相邻顶点 u,v，对 G 进行添边操作和粘合操作，反复进行这个过程，直至获得完全图为止。设最终得到的阶数最小的完全图为
m
K,则由定理 6.4.2,mG =)(χ 。对该完全图进行顶点正常 m 染色，并进行反向操作，便可得图 G 的顶点正常 m 染色。
根据定理 6.4.2，添边粘合算法的运行结果是顶点染色问题的精确解。但添边粘合法的执行过程是一棵二叉树，因此其计算复杂性是指数阶的。
例 6.4.2 求下图 G 的色数，及顶点正常 (G)χ 染色。
解：添边和粘合运算过程如下所示。
u
v
u
v
u v
G
G′
G′′
G
G
11
由于最终得到的阶数最小的完全图为
3
K,故 3)( =Gχ 。 对该
3
K 的 3 个顶点分别染色 1,2，
3。然后反向操作，每次相当于将先前粘合起来的点分开，分出来的两点与原来的点染相同
的颜色。这样得到 G 的一个顶点 3 正常染色如下。
z 规范染色法（极大独立集法）
设 },,,{
21 k
VVV null=? 是图 G 的点 k 染色。若
1
V 是 G 的极大独立集，
2
V 是
1
\ VG 的极大独立集，
3
V 是 )(\
21
VVG ∪ 的极大独立集，……，一般地，
i
V 是
∪
1
1
\
=
i
j
j
VG 的极大独立集
（ ki null,3,2= ）,则称? 是图 G 的 规范 k 染色 （ canonical k-colouring）,
定理 6.4.3 图 G 是顶点可 k 正常染色的当且仅当 G 存在规范 k 染色。
证明：充分性是显然的。
必要性,设 },,,{
21 k
VVV null 是图 G 的一个顶点正常 k 染色,则
k
VVV,,,
21
null 都是 G 的独立集。
若
1
V 不是 G 的极大独立集，则可从
1
\ VV 中调一些顶点进入
1
V,使
1
V 扩大成 G 的极大独立集
)1(
1
V,
k
VVV,,,
32
null 变成
)1()1(
3
)1(
2
,,,
k
VVV null 。然后考虑
)1(
2
V 。若它不是
)1(
1
\ VG 的极大独立集，则可从 )(\
)1(
2
)1(
1
VVV ∪ 中调一些顶点进入
)1(
2
V,将其扩充成
)1(
1
\ VG 的极大独立集
)2(
2
V,
)1()1(
3
)1(
2
,,,
k
VVV null 变成
)2()2(
3
)2(
2
,,,
k
VVV null 。如此类推，最后可得图 G 的规范 k 染色
)()2(
2
)1(
1
,,,
k
k
VVV null 。 证毕。
规范染色法基本思想,求 G 的极大点独立集
1
V,将其顶点都染上色 1；再求
1
\ VG 的极大点独立集
2
V,将其顶点都染上色 2；如此类推，直至染完所有顶点。
规范染色法步骤,
输入：图 G 及其邻接矩阵，输出,G 的顶点正常色划分（独立集划分）,
12
,,,
k
VV Vnull 。
第 0 步,SV=,,1i =,
第 1 步,任取 x S∈,{},( {}) ( )
i
VxTSxNx==?∩：：，转下步。
第 2 步,若 T φ=,输出
i
V,并令
i
SSV=?,转第 4 步；否则，转第 3 步。
第 3 步,任取 y T∈,{},( {}) ( )
ii
VV yT T y Ny==?∩∩，转第 2 步。
第 4 步,若 S φ=,停止；否则，令,1ii= +,转第 1 步。
1
2
3
3
1
12
算法第 1 步至第 4 步反复循环，第 i 次循环得到极大独立集 V
i
。在第 i 次循环中，第 2
步到第 3 步反复循环向 V
i
中添加不相邻顶点，使其成为极大独立集。在算法中,()Nx表示顶点 x 的不相邻顶点集。集合 S 表示除了以得到的极大独立集之外，剩余的顶点集。 T 纪录在形成极大独立集 V
i
的过程中,尚未进入
12
,,,
i
VV Vnull 且与已进入 V
i
的顶点不相邻的顶点之集。算法结束时，得到图 G 的顶点正常色划分（独立集划分）,
12
,,,
k
VV Vnull 。
注,（ 1）这是一种贪婪算法。
（ 2）规范 k 染色一般不唯一。
（ 3）运行一次这个算法能得到图 G 的一种正常顶点染色，但它所用的颜色数未必就是
)(Gχ 。因此该算法是一个近似算法。
（ 4）由定理,G 可用 )(Gχ 种颜色正常顶点染色，则必存在 )(Gχ 规范染色。因此只需从一切规范染色中选出颜色数最少者，即可求得 )(Gχ 。但由于需要枚举所有规范染色才能确定出 )(Gχ,故用该方法求 )(Gχ 不是多项式时间算法，只适用于阶数较小的图。
例 6.4.3 对下图 G，利用规范染色法求其色数 (G)χ 的近似值及相应的顶点染色。
解,G 的一个极大独立集为 },,{
1
cgaV =,
1
\ VG 的一个极大独立集为 },,{
2
fdbV =,
)(\
21
VVG ∪ 的一个极大独立集为 }{
3
eV = 。故 G 可正常 3 顶点染色,3)( ≤Gχ 。相应的顶点 3 正常染色如下所示,
注,对本题所给的图 G，上述过程恰好得到 (G)χ 。事实上，因 G 含有
3
K,因此正常顶点染色至少需要 3 种颜色。从而 3)( =Gχ 。
z 顺序染色法
算法思想：将图 G 的顶点排一个顺序
n
vvv,,,
21
null 。先给顶点
1
v 染上色
1
c 。对顶点
2
v,
从颜色集合 },,,{
321
nullccc 中选取未被
2
v 的邻点使用的编号最小的色来染它。一般地，对顶
a
c
d
bf
e
g
a
c
d
bf
e
g
1
3
1
1
2
2
2
13
点
i
v,从颜色集合 },,,{
321
nullccc 中选取未被
i
v 的邻点使用的编号最小的色给其染色，
ni,,2,1 null= 。
算法步骤,
第 1 步：令 1:=i 。
第 2 步：令 1:=c 。
第 3 步：若对所有 )(
i
vNy∈,颜色 c 未染 y，则令 c 染
i
v,转第 5 步。
第 4 步,1,+= cc,转第 3 步。
第 5 步：若 ni <,则 1,+= ii,转第 2 步；否则，停止。
例,
注,（ 1）顺序染色法是多项式时间算法，时间复杂性为 )(
2
nO 。
（ 2）顺序染色法是一种近似算法，其算法结果（所用颜色数）与顶点的标号顺序有密切关系。比如，对完全二部图 ),(
,
YXK
nn
=,若顶点标号顺序为
nn
yyyxxx,,,,,,,
2121
nullnull,
则算法结果只用两种颜色，是最优解。但若顶点顺序为
nn
yxyxyx,,,,,,
2211
null,则算法结果需 n 种颜色。算法近似比
2
~
*
n
c
c
=,无界！
z Welsh-Powell 算法 (最大度优先算法 )
第 1 步：将图 G 的顶点按度数递减的顺序排列，设为
n
vvv,,,
21
null 。
第 2 步：用第 1 种颜色给
1
v 染色，令 }{:
1
vV
c
=,1:=i 。
第 3 步：若存在与
c
V 中所有点都不相邻的未染色顶点，则找出第一个与
c
V 中所有点都不相邻的未染色顶点 v，转下步；否则 1,+= ii,转第 5 步。
第 4 步：给 v 染上第 i 种色，令 }{,vVV
cc
∪=,转第 3 步。
第 5 步：取尚未染色的顶点中编号最小的顶点 v，令 }{,vV
c
=,转第 3 步。
第 6 步：所有顶点都得到染色时，停止。
例,
v
1
v
3
v
4
v
2
v
6
v
5
v
7
v
7
v
6
v
5
v
2
v
3
v
4
v
1
14
图的染色是内容十分丰富而又应用广泛的一个图论专题。 关于染色问题可进一步参考文献 [116]~[91]。其 中 [116]~[118]是与图染色问题有关的专著,[119]~[120]是与图染色有关的网页,[121]~[122]讨论图的边染色,[123]~[125] 研究有约束的图染色问题,[126]~[127]研究赋权染色问题,[128]~[129]涉及图的色幂（ coloring powers）,[130]~[134]与随机图染色和随机算法有关,[135]~[138]研究全染色和全色数（ total-coloring）,[139]~[142]研究表色数
（ list-coloring）,[143]~[150]涉及图的和染色（ sum coloring）及相关算法的性能,[151]~[167]
研究其他与图的染色有关的问题,[168]~[171]研究染色问题在寄存器配置中的应用，
[172]~[180]是有关染色问题在通信网络优化、地理信息系统等方面的应用。
[116] Reinhard Diestel,Graph Theory,Springer,1997,
[117] Tommy R,Jensen and Bjarne Toft,Graph Coloring Problems,Wiley-Interscience,New
York,1995,
[118] B,Toft,75 graph-colouring problems,in Graph Colourings (R,Nelson and R.J,Wilson,
Eds.),Wiley,New York,(1990),pp9-35,
[119] http://www.nada.kth.se/~viggo/problemlist/
[120] http://web.cs.ualberta.ca/~joe/Coloring/#Links.other
[121] L.D,Andersen,On edge-colourings of graphs,Math,Scand,40(1977),pp161-175,
[122] N,Rorbertson,P,D,Seymour and R,Thomas,Tutte’s edge-coloring conjecture,J,Combin,
Theory (Ser,B),70(1997),pp166-183,
[123] N,Alon,Restricted colorings of graphs,in Surveys in Combinatorics 1993 (Proc,14
th
British Combinatorial Conference),Cambridge Univ,Press,Cambridge,(1993),pp1-33,
[124] H.R,Hind,Restricted Edge-Colourings,Ph.D,thesis,University of Cambridge,1988,
[125] M,Caramia and P,Dell'Olmo,Constraint propagation in graph coloring,Journal of
Heuristics,8(1) (2002),pp83-107,
[126] Egon Balas and Jue Xue,Minimum weighted coloring of triangulated graphs,with
application to maximum weight vertex packing and clique finding in arbitrary graphs,SIAM
Journal on Computing,20(2) (1991),pp209-221,
[127] M,Caramia and P,Dell'Olmo,Solving the minimum-weighted coloring problem,Networks,
38(2) (2001),pp88-101,
[128] D,Král',Coloring Powers of Chordal Graphs,SIAM J,Discrete Math.,18(2004-2005),
pp451-461,
[129] G,Agnarsson and M,M,Halldórsson,Coloring Powers of Planar Graphs,SIAM J,Discrete
Math.,16(2002-2003),pp651-662,
[130] R.Motwani and P,Raghavan,Randomized Algorithms,Cambridge University Press,New
York,1995,
[131] U,Feige,Randomized graph products,chromatic numbers,and the Lovász?-function,in
Proceedings of the 27
th
Annual ACM Symposium on Theory of Computing,(1995),635-640,
[132] T,Luczak,The chromatic number of random graphs,Combinatorica,11(1) (1991),
pp45-54,
[133] M,Fürer and C,R,Subramanian,Coloring random graphs,In Proceedings 3rd
15
Scandinavian Workshop on Algorithmic Theory,Berlin,1992,Springer Lecture Notes in
Computer Science,
[134] Cécile Murat,Vangelis Th,Paschos,On the probabilistic minimum coloring and minimum
k-coloring,Discrete Applied Mathematics,154(2006),pp564-586,
[135] V,A,Bojarshinov,Edge and total coloring of interval graphs,Discrete Applied Mathematics,
114(2001),pp23-28,
[136] O.V,Borodin,On the total coloring of planar graphs,J,Reine Angew,Math.,394(1989),
pp180-185,
[137] D.L,Chen and J,L,Wu,The total coloring of some graphs,in,Combinatorics,Graph
Theory,Algorithms,and Applications,Beijing,1993”,World Science,River Edge,NY,(1994),
pp17-20,
[138] Celina M.H,de Figueiredo,J,Meidanis,and C,P,De Mello,Total-Chromatic number and
chromatic index of dually chordal graphs,Information Processing Letters,70(1999),pp147-152,
[139] A,Daneshgar and H,Hajiabolhassan,Unique list-colourability and the fixing chromatic
number of graphs,Discrete Applied Mathematics,152(2005),pp123-138
[140] O.V,Borodin and A.V,Kostochka,List edge and list total colorings of multigraphs,Journal
of Combinatorial Theory (Ser,B),71(1997),pp184-204,
[141] F,Galvin,The list chromatic index of a bipartite multigraph,Journal of Combinatorial
Theory (Ser,B),63(1995),pp153-158,
[142] J,Kahn,Asymptotically good list-colorings,J,Combin,Theory (Ser,A),73(1996),pp1-59,
[143] M,R,Salavatipour,On sum coloring of graphs,Discrete Applied Mathematics,127(2003),
pp477-488,
[144] Bar-Noy,A.,Bellare,M.,Halldórsson,M,M.,Shachnai,H.,and Tamir,T,(1998),On
chromatic sums and distributed resource allocation,Inform,and Comput,140,183-202,
[145] Bar-Noy,A.,Halldórsson,M,M.,Kortsarz,G.,Shachnai,H.,and Salman,R,(1999),Sum
multicoloring of graphs,Proc,7th Ann,European Symp,on Algorithms,Lecture Notes in Comput,
Sci.,Springer-Verlag,
[146] Bar-Noy,A.,and Kortsarz,G,(1998),The minimum color sum of bipartite graphs,J,
Algorithms 28,339-365,
[147] Halldórsson,M,M.,and Kortsarz,G,(1999),Multicoloring planar graphs and partial k-trees,
Proc,2nd Int,Workshop on Approximation Algorithms for Combinatorial Problems,Lecture
Notes in Comput,Sci.,Springer-Verlag,
[148] Halldórsson,M,M.,Kortsarz,G.,Proskurowski,A.,Salman,R.,Shachnai,H.,and Telle,J,
A,Multi-coloring trees,Proc,5th Ann,Int,Conf,on Computing and Combinatorics,Lecture
Notes in Comput,Sci.,Springer-Verlag,(1999),271-280,
[149] Jansen,K,(2000),Approximation results for the optimum cost chromatic partition problem,
J,Algorithms 34,54-89,
[150] S,Nicoloso,X,Song,M,Sarrafzadeh (1999),On the sum coloring problem on interval
graphs,Algorithmica 23,109-126,
[151] H,Enomoto,M,Hornák,and S,Jendrol',Cyclic chromatic number of 3-connected plane
graphs,SIAM J,Discrete Math.,14(2001),pp121-137,
16
[152] Oleg V,Borodin and Douglas R,Woodall,Cyclic colorings of 3-polytopes with large
maximum face size,SIAM J,Discrete Math.,15(2001-2002),pp143-154,
[153] M,Larsen,J,Propp,and D,Ullman,The fractional chromatic number of Mycielski’s graphs,
J,Graph,Theory,19(1995),pp411-416,
[154] G,Chartrand,L,Nebesky and P,Zhang,Hamiltonian colorings of graphs,Discrete Applied
Mathematics,146(2005),pp257-272
[155] M,O,Albertson,A,V,Kostochka,and D,B,West,Precoloring Extensions of Brooks'
Theorem,SIAM J,Discrete Math.,18(2004-2005),pp542-553,
[156] J,Janssen and K,Kilakos,Bounded Stable Sets,Polytopes and Colorings,SIAM J,Discrete
Math.,12(1999),pp262-275,
[157] G,Bacsó,S,Gravier,A,Gyárfás,M.,Preissmann,and A,Sebo,Coloring the Maximal
Cliques of Graphs,SIAM J,Discrete Math.,17(2003-2004),pp361-376,
[158] Chaudhary,A.,and Vishwanathan,S,(1997),Approximation algorithms for the achromatic
number,Proc,8th Ann,ACM-SIAM Symp,on Discrete Algorithms,ACM-SIAM,558-563,
[159] V,Guruswami and S,Khanna,On the Hardness of 4-Coloring a 3-Colorable Graph,SIAM J,
Discrete Math.,18(2004-2005),pp30-40,
[160] A,Gyárfás,Z,Király,and J,Lehel,On-Line 3-Chromatic Graphs I,Triangle-Free Graphs,
SIAM J,Discrete Math.,12(1999),pp385-411,
[161] N,Alon and M,Krivelevich,Testing k-colorability,SIAM J,Discrete Math.,15(2001-2002),
pp211-227,
[162] A,Hertz,B,Jaumard,and M,P,de Aragao,Local optima topology for the k-coloring
problem,Discrete Applied Mathematics,49(1-3) (1994),pp257-280,
[163] J,Fiala,K,Jansen,V,B,Le,and E,Seidel,Graph Subcolorings,Complexity and
Algorithms,SIAM J,Discrete Math.,16(2002-2003),pp635-650,
[164] U,Feige,M,Langberg,and G,Schechtman,Graphs with Tiny Vector Chromatic Numbers
and Huge Chromatic Numbers,SIAM J,Computing,33(2003-2004),pp1338-1368
[165] M,Vasquez,New results on the queens_n
2
graph coloring problem,Journal of Heuristics,
10(4) (2004),pp407-413,
[166] J,Culberson and I,P,Gent,Frozen development in graph coloring,Theoretical Computer
Science,265(1-2) (2001),
[167] A.V,Gelder,Another look at graph coloring via propositional satisfiability,(2002),48-54,
Ithaca,New York,USA,
[168] G,Chaitin,Register allocation and spilling via graph coloring,SIGPLAN Not.,39(4) (2004),
pp66-74,
[169] Fred C,Chow and John L,Hennessy,The priority-based coloring approach to register
allocation,ACM Transactions on Programming Languages and Systems,12(4) (1990),pp501-536,
[170] Allen M.,Kumaran G.,and Liu T,(2002),A combined algorithm for graph-coloring in
register allocation,pp,100-111,Ithaca,New York,USA,
[171] M.D,Smith,N,Ramsey,and G,Holloway,A generalized algorithm for graph-coloring
register allocation,In PLDI '04,Proceedings of the ACM SIGPLAN 2004 Conference on
Programming Language Design and Implementation,(2004),pp277-288,ACM Press,New York,
NY,USA,
17
[172] S,Gerke,Weighted colouring and channel assignment,DPhil thesis,University of Oxford,
2000,
[173] C,Mcdiarmid,and B,Reed,Channel assignment and weighted colouring,Networks,
36(2000),pp114-117,
[174] A,Zymolka,A.M.C.A,Koster,and R,Wess?ly,Transparent optical network design with
sparse wavelength conversion,In Proceedings of the 7th IFIP Working Conference on Optical
Network Design & Modelling,(2003),pp 61-80,Budapest,Hungary,
[175] C,Nomikos,A,Pagourtzis and S,Zachos,Routing and path multicoloring,Information
Processing Letters,80(2001),pp249-256,
[176] Hung Q,Ngo and Van H,Vu,Multirate Rearrangeable Clos Networks and a Generalized
Edge-Coloring Problem on Bipartite Graphs,SIAM J,Computing,32(2002-2003),pp1040-1049,
[177] Andreas Gamst,Some lower bounds for a class of frequency assignment problems,IEEE
Transactions of Vehicular Echnology,35(1) (1986),pp8-14,
[178] M,R,Garey,D,S,Johnson,and H,C,So,An application of graph coloring to printed
circuit testing,IEEE Trans,on Circuits and Systems,CAS-23 (1976),pp591-599,
[179] N,Barnier and P,Brisset,Graph coloring for air traffic flow management,In CPAIOR'02,
Fourth International Workshop on Integration of AI and OR Techniques in Constraint
Programming for Combinatorial Optimisation Problems,(2002),pp133-147,Le Croisic,France,
[180] R,Freimer,Generalized map coloring for use in geographical information systems,In
ACM-GIS 2000,Proceedings of the Eighth ACM Symposium on Advances in Geographic
Information Systems,edited by K.J,Li,K,Makki,N,Pissinou,and S,Ravada,(2000),pp167-173,
ACM press,New York,NY,USA,
