1
第六章 染色理论
许多实际问题可以归结为求图的匹配或者独立集。 此外,在许多应用中,人们希望知道：
一个给定的图,它的边集至少能划分成多少个边不交的匹配？或它的顶点集至少能划分成多少个点不交的独立集？这便是图的边染色和顶点染色问题。
§ 6.1 边染色
定义 6.1.1 非空无环图 G 的 边正常 k 染色 （ proper edge k- colouring）是 指 k 种颜色 12,knull，，
对 E(G)中元素的一种分配，使得相邻两条边所染颜色不同。换句话说,G 中边正常 k 染色
是映射
},,2,1{)(,kGEc null→,
使得对每个 i ( ki,,2,1 null= ),)(
1
ic
是匹配或者空集。
注,若 令 ),,2,1(},)()({)(
1
kiiecGEeicE
i
null==∈==
，则 G 的一个边正常 k 染色可看成是边集的一种划分 ),,,(
21 k
EEEc null=,其中每个 E
i
是匹配或空集。
例如，下面给出了 5-圈的一种边正常 3 染色和 Petersen 图的一种边正常 4 染色。
定义 6.1.2 若存在 G 的一种边正常 k 染色，则称 G 是 边 k 色可染的 （ edge k-colourable） 。
注,（ 1）每个无环非空图的边必 ε 色可染。
（ 2）若 G 是边 k 色可染的，则对 kl ≥?,G 也是 l 色可染的。
定义 6.1.3 正整数 GkG min{)( =′χ 是边 k 色可染的 }称为 G 的 边色数 (edge chromatic
number)。
注,（ 1）若 kG ＝)(χ′,则 G 中边的任何 k 染色 ),,,(
21 k
EEEc null= 中每个 E
i
都是非空的匹配。
（ 2） G 的边色数 )(Gχ′ 是 G 中边不交匹配的最小数目。
（ 3） )(12)(
22 nn
KnK Δ=?=′χ （因完全图 K
2n
有 2n-1 个边不交的匹配）
（ 4） )()( GG Δ≥′χ 。 （设 )()( Gvd Δ=,则与 v 关联的 )(GΔ 条边至少需 )(GΔ 种色才能正常染色） 。
引理 6.1.1,设 G 是非空无环的连通图，且不是奇圈，则存在 G 的边 2-染色，使得所用的两种色在每个度 2≥ 的顶点处都出现。
证明,（ 1）设 G 是 Euler 图，则 G 中无奇度点。
若 G 本身是一个偶长度圈，则命题显然。若 G 不是一个偶长度圈，则 G 至少有一个顶点 v
0
满足 4)(
0
≥vd (否则,G 中所有顶点都是 2 度的，由于 G 连通，从而 G 是圈，由引理条件,G 不是奇圈，故为偶圈，矛盾 )。
3
3 4
1
1
3
2
2
31
1
2
4
2 2
3
2
1
1
2
2
设
02110
veevev
ε
null 是 G 的一条 Euler 闭迹。 令 ieE
i
{
1
= 为奇数 },ieE
i
{
2
= 为偶数 }。
于是 c = (E
1
,E
2
) 即为所求的边 2-染色。
需要说明的是,Euler 闭迹从度≥ 4 的顶点出发是必需的。例如在下图中，若从 2 度顶点 u 处出发沿 Euler 闭迹交替地对边进行 2 染色，则 u 点可能仅能获得一种色（如图,1,2
表示两种颜色） 。
(2) 设 G 不是 Euler 图。此时给 G 增添一个新顶点 v
0
，将 v
0
与 G 的每个奇度顶点连一条边，得到一个新图 G
*
。显然 G
*
的所有顶点都是偶数度的，因而是 Euler 图。设
0*)(2110
veevev
Gε
null 是 G
*
的一个 Euler 闭迹，令 ieE
i
{
*
1
= 为奇数 },ieE
i
{
*
2
= 为偶数 }，这样可得 G
*
的一个边 2-染色 ),(
*
2
*
1
*
EEc =,（其中
0
v 点的关联边有可能是同一种色） 。按这种办法给 G
*
的边染色后，去掉
0
v 及其关联的边，便得到 G 的一个边 2-染色。对于 G 中偶度点，它关联的边及其颜色与 G
*
中相同；对 G 的任何奇度点 v，在 G 中比在 G
*
中少关联一条边，但只要 1)( >vd
G
,便有 3)( ≥vd
G
,故由染色的方法知，与 v 点关联的边中两种颜色的都有。这说明 G 的边 2-染色 ))(),((
*
2
*
1
GEEGEEc ∩∩= 即为所求的边 2-染色。证毕。
定义 6.1.4 对于 G 的一个边 k-染色 c,c(v)表示顶点 v 处出现的不同颜色的数目。设 c 与 c′
都是 G 的边 k-染色（未必是正常染色） 。若相应的 c(v)与 )(vc′ 满足,
∑∑
∈∈
>′
)()(
)()(
GVvGVv
vcvc,
则称 c′是对 c 的一个 改进 。不能改进的边 k 染色称为 最佳边 k 染色 。
引理 6.1.2 设 ),,,(
21 k
EEEc null= 是 G 的一个最佳边 k 染色,且存在一个顶点 u 及两种颜色
i 和 j,色 i 不在 u 处出现，而色 j 在 u 处出现了至少两次，则 ][
ji
EEG ∪ 中含 u 的连通分支必是奇圈。
证明,设 G
1
是 ][
ji
EEG ∪ 中含 u 的连通分支。若 G
1
不是奇圈，则由引理 6.1.1,G
1
有一个边-2 染色，其两种色在 G
1
中度 2≥ 的每个顶点处都出现。按这种染色办法用色 i 和 j 给
ji
EE ∪ 中的边重新染色后，得到 G 的一个新的边 k-染色 ),,,(
21 k
EEEc ′′′=′ null,其中 i,j
两色都在 u 处出现，故 1)()( +=′ ucuc,而对 u 之外的其它顶点 v，都有 )()( vcvc ≥′ 。于是
∑∑
∈∈
>′
)()(
)()(
GVvGVv
vcvc 。这与 c 是最佳边 k-染色矛盾。证毕。
定理 6.1.1（ K?nig
[1]
,1916）设 G 是二部图，则 () ()GGχ′ =Δ 。
[1] D,K?nig,über Graphen und ihre Anwendung auf Determinantentheorie und mengenlehre,
Math,Ann.,77(1916),453-465,
证明 （反证法）,假设 () ()GGχ′ ≠Δ 。则由定义 6.1.3 的注（ 4）,() ()GGχ′ >Δ 。设
),,,(
21 Δ
= EEEc null 是 G 的一个最佳边 Δ 染色，则 c 必定不是正常染色。故存在顶点 u 满足 )()( uduc <,因而必有某两条在 u 点相邻的边染了同一种色。 而且,因 () ( )du G≤Δ,故
u
1 2
1 2
1
1
2
3
Δ 种色中必有某种色不在 u 上出现。显然 u 满足引理 6.1.2 的条件，因此 G 中有奇圈。这与
G 是二部图矛盾。证毕。
注,也可按推论 3.3.3，二部图的边集可分解为 )(GΔ 个边不交的匹配，故 () ()GGχ′ =Δ 。
定理 6.1.4 (Vizing 定理,1964) 设 G 是无环非空简单图，则
1)()()( +Δ≤′≤Δ GGG χ 。
证明,首先,)()( GG Δ≥′χ (定义 6.1.3 的注（ 4） )。下证 1)()( +Δ≤′ GGχ (用反证法 )。
假如 1)()( +Δ>′ GGχ,令 ),,,(
121 +Δ
= EEEc null 是 G 的最佳 1+Δ 边染色。因
1+Δ>′χ,故 c 必不是正常染色。设 u 是使 )()( uduc < 的顶点。则必存在色 i
0
,i
0
不在 u
处出现（因 1)( ＋Δ<ud ）,同时也存在色 i
1
,i
1
至少在 u 处出现两次。设 uv 和 uv
1
染有颜色 i
1
（如图） 。
因 1)(
1
+Δ<vd,故必有某种色
2
i 不在 v
1
处出现。这样
2
i 必然在 u 处出现（否则，可用
2
i 给 uv
1
重新染色，得到一个改进的 1＋Δ 边染色，与 c 是最佳染色矛盾） 。因此存在一条边 uv
2
染有色
2
i 。
又因 1)(
2
+Δ<vd,必有某种色
3
i 不在 v
2
处出现。
3
i 必然在 u 处出现 （理由同上） 。
因此存在一边 uv
3
染有色
3
i 。
继续这个过程，可找出一个顶点序列 null,,
21
vv,以及一个颜色序列 null,,
21
ii,使得边 uv
j
染有颜色 i
j
，且色 i
j+1
不在点 v
j
处出现,（ null,2,1=j ） 。而且，因 )()( uduc < 且 )(ud 是有限数，故存在一个最小整数 m，使得对某个 k < m，有 i
m+1
= i
k
。
现在，对 11?≤≤ kj,用颜色 i
j+1
给边 uv
j
重新染色。这样产生一个新的 ( 1＋Δ )边染色
),,,(
121 +Δ
′′′=′ EEEC null 。显然对所有 Vv∈,)()( vcvc ≥′ 。因此 c′也是 G 的一个最佳
)1( +Δ 边染色。由引理 6.1.2,][
0 k
ii
EEG ′′ ∪ 中含有 u 的那个分支
1
H 是个奇圈。
…
u
v
v
3
v
2
v
1
v
k
v
k-1
v
m
i
1
i
1
i
2
i
m
i
k-1
i
k
i
3
…
…
…
u
v
v
3
v
2
v
1
v
k
v
k-1
v
m
i
1
i
2
i
3
i
m
i
k-
i
k
i
4
…
…
i
0
i
0
i
k
i
k
H
1
4
而对 1?≤≤ mjk,用颜色 i
j+1
给 uv
j
重新染色，而用颜色 i
k
给 uv
m
重新染色，得到一个 ( 1＋Δ )边染色 ),,,(
121 +Δ
′′′′′′=′′ EEEc null 。同理有 )()( vcvc ≥′′ 对所有 Vv∈ 成立。故由引理
6.1.2,][
0 k
ii
EEG ′′′′ ∪ 中含有 u 的分支
2
H 是个奇圈。
但是，因 v
k
在
1
H 中的度为 2（恰与一条 i
0
色边和一条 i
k
色边相关联）,故它在
2
H 中的度为 1（仅与一条 i
0
色边相关联） 。这与
2
H 是奇圈矛盾。 （注意 v
k
必在分支
2
H 中，因它与
v
k
－
1
有 i
0
,i
k
交错路（
1
H 的一段）相连） 。由此可知反证法假设不能成立。证毕。
对于有重边的图 G，设 )(Gμ 表示 G 中边的最大重数,Vizing 实际上证明了一个更一般的结论,)()()()( GGGG μχ +Δ≤′≤Δ 。
Vizing 定理提出了一个分类问题：使 )()( GG Δ=′χ 的简单图称为第一类图，使
1)()( +Δ=′ GGχ 的简单图 G 称为第二类图。确定一个图属于第一类还是第二类是很困难的，目前仅对少量的图类判明了它们所属的类。路、树、二部图、偶数阶完全图、轮图都是第一类图（轮图
1,n
W 是由一个点与长为 n 的圈上所有顶点相连形成的图）,奇圈、奇数阶完全图都是第二类图 (见有关定理和习题 )。一般情况下判别一个图属于第几类图，尚没有好的充分必要判别条件，一些充分性判别条件见习题。
第二类图相对较稀少。在 6υ ≤ 的 143 个连通简单图中仅有 8 个属于第二类；而 Erd?s
和 Wilson(1977)已证明,1
|)()(|
|)(|
lim
21
1
=
∞→
νν
ν
cc
c
v
∪
，其中 ()
i
c υ 表示 υ阶第 i 类图的集合。这表明当顶点数充分大时，几乎所有非空简单图都是第一类图。
已经知道存在最大度为 2,3,4,5 的第二类平面图，但 Vizing (1965)已证明：不存在最大度 8≥ 的第二类平面图。目前尚不知道是否存在最大度为 6 或 7 的第二类平面图。
由 Vizing 定理，每个无环非空简单图 G 都是可（ 1+Δ ）边可染色的。实际上，可以根据引理 6.1.1 和引理 6.1.2 给出求图 G 的正常（ 1+Δ ）边染色的多项式时间算法。但是，求一般图 G 的边色数 )(Gχ′ 及其相应的正常边染色尚无多项式时间算法。事实上，已经证明这是一个 NPC 问题
[2]
。求二部图的边色数的一个多项式时间算法将在§ 6.4 中介绍。有关边染色的更多内容可参看 [3]。
[2] I,Holyer,The NP-completeness of edge-coloring,SIAM J,Computing,10(1981),718-720,
[3] S,Fiorini,and R.J,Wilson,Edge-colorings of graphs,Selected Topics in Graph Theory (eds,L,
W,Beineke,and R.J,Wilson),Academic Press,London,(1978) 103-126,
…
u
v
v
3
v
2
v
1
v
k
v
k-1
v
m
i
1
i
2
i
3
i
m
i
k-
i
k
＋
1
i
4
…
…
i
0
i
0
i
k
i
k
H
2
i
k
5
§ 6.2 点染色
一、点染色的基本概念
定义 6.2.1 设 G 是一个无环边的图。 G 的顶点 正常 k 染色 (proper vertex k-colouring)π 是指 k
种颜色 12,knull，，对于 G 的各顶点的一种分配，使得任二相邻的顶点被染上不同的颜色。换句话说,G 的顶点正常 k 染色 π 是一个映射
},,2,1{)(,kGV null→π,
使得 )(
1
i
π 是独立集或空集 ),,2,1( ki null=,
注,设 π 是 G 的一个顶点正常 k 染色。令
})(|)({)(V
1
ixGVxi
i
=∈==
ππ,（ ki,,2,1 null= ） 。
则 π 实际上是对顶点集 )(GV 的一种划分,),,,(
21 k
VVV null=π,其中 φ=
ji
VV ∩,
)(
1
GVV
k
i
i
=
=
∪
，且每个
i
V 是独立集或空集 ),,2,1( ki null=,
例如，下图给出了 Petersen 图的一种定点正常 3 染色。
定义 6.2.2 若存在 G 的一种顶点正常 k 染色,则称图 G 是 点 k 色可染的 (vertex k-colourable),
有时简称为 k 色可染的 或 可 k 染色的 。
注,⑴ 每个图 G 一定是 ()Gυ 色可染的。
⑵ 若图 G 是 k 色可染的，则对任何正整数 km ≥,G 也 m 色可染。
定义 6.2.3 设 G 是无环边的图，令
GkG |min{)( =χ 是 k 色可染的 },
称 )(Gχ 为 G 的 点色数,有时简称为 色数 (chromatic number)。若 kG =)(χ,则称 G 为 k 色图 (k-chromatic graph)。
注,（ 1） 若 kG =)(χ （即 G 是 k 色图）,则 G 中任何点 k 染色 ),,,(
21 k
VVV null=π 中每个
i
V 都是非空的独立集。换言之,G 的色数是 G 中点不交的独立集的最小数目。
（ 2）由色数的定义容易证明如下结论,
z 1)( =Gχ? GK
υ
= ；
z 2)( =Gχ?G 是非空二部图；
z 3)(
12
=
+n
Cχ 。
z 3)( ≥Gχ? G含有奇圈。
z () ()GGχ υ=? GK
υ
。
1
1
3
3
2
2
3 1
1
2
6
点染色理论的基本问题,给定图 G，确定 )(Gχ 的值。
目前,人们仅对某些特殊图类,确定出了计算 )(Gχ 的公式。 对一般图 G,得出了 )(Gχ
的各种上下界。为了介绍有关结果，需要引入色临界图的概念。
二、色临界图
定义 6.2.4 设 )1(,)( ≥= kkGχ 。若对 G 的任何真子图 H，均有 kH <)(χ,则称 G 是 临界
k 色图 （ critical k-chromatic graph）,
注,临界 k 色图实际上就是 k 色极小子图，也就是说，它本身是 k 色的，但任意删去一个顶点或一条边后色数就会减少。按色临界图的概念容易知道下列结论成立
z 3)( ≥Gχ? G含有奇圈。
z G 是临界 1 色图?
1
G K? ；
z G 是临界 2 色图?
2
G K? ；
z G 是临界 3 色图?G 是奇圈；
此外，容易证明,（1）任何 k 色图都包含临界 k 色子图； （2）每个色临界图都是连通的简单图。 （留作习题） 。
定理 6.2.1 色临界图的顶点割集不是团。
证明（反证法）,假设图 G 是一个临界 k 色图，但有一个点割集 S 是团。记 SG \ 的连通分支为
n
GGG,,,
21
null 。将 ][SG 按 G 中的连接方式分别与
n
GGG,,,
21
null 相连，得到子图
n
GGG ′′′,,,
21
null 。
示例:图 G 及点割集 S={u,v}
321
,,GGG ′′′
因 G 是 k 色临界的,故每个
i
G′是 k－ 1 色可染的。 由于 S 是团,所以 S 中各个顶点在
i
G′
的任何 k－ 1 染色中必染到相异的色。我们总可以调整各
i
G′中颜色的编号，使得 S 中每一个顶点在各
i
G′中染相同的色。这些
i
G′的染色合在一起便形成 G 的一个 k－ 1 染色。这与 G 是临界 k 色图矛盾。证毕。
推论 6.2.1 每个色临界图都是块（即不含割点，亦即 2 连通） 。
证明：假如某临界图不是块，则它有割点。这个割点构成一个团，与定理 6.2.1 矛盾。证毕。
下一个推论是显然的。
推论 6.2.2 若临界 k 色图 G 有 2 顶点割集 },{ vu,则 u 与 v 不相邻。
u
v
u
v
u
v
u
v
7
定理 6.2.2 (Dirac,1952) 设 G 是临界 k 色图（ k≥2）,则边连通度 1)(?≥′ kGκ 。
证明：若 k = 2，则
2
KG?,故 1)( =′ Gκ 。
下设 3≥k,用反证法。
假如 1)(?<′ kGκ,则存在 )(GVS? 使得 1)(|),(|?<′= kGSS κ 。因 G 是临界 k
色图，故 ][
1
SGG = 与 ][
2
SGG = 中的顶点都 1?k 色可染。设 ),,,(
1211?
=
k
UUU nullπ 和
),,,(
1212?
=
k
WWW nullπ 分别是
1
G 和
2
G 中点的 1?k 染色。构造二部图
),( YXH =,},,{
1,21?
=
k
xxxX null,},,{
1,21?
=
k
yyyY null,
其中?∈ )(HEyx
jii
U 的点与
j
W 的点在 G 中无连边。
因 1)(|),(|?<′= kGSS κ,故 )2)(1()1()1()(
2
=> kkkkHε 。（注意 X 与
Y 间共可连出
2
)1(?k 条可能的边；其次，因在 G 中 S 与 S 间连边数 1?< k,故 X 与 Y 间在 H 中不能连的边数 1?< k ） 。
我们来证明 H 必有完美匹配。
事实上,H 的点覆盖数 1)(?≥ kHβ （否则，若 2)(?≤ kHβ,则因 1)(?≤Δ kH,H
的每个顶点至多能覆盖 1?k 条边。这样 )1)(2()1()()(≤≤ kkkHH βε,与
)2)(1()(> kkHε 矛盾） 。由 K?nig 定理（第五章定理 5.2.2）,1)()(?≥=′ kHH βα 。
这表明 H 有完美匹配（因对于 H,1?== kYX ） 。
设 H 的一个完美匹配为 M
*
,}1,,2,1{
*
== kiyxM
i
ji
null,相应地
i
jii
WUV ∪=,
则 V
i
是 G 的独立集（ 1,,2,1?= ki null ）,因此 ),,,(
121?
=
k
VVV nullπ 是 G 的一个点 k-1 染色。
但这与 kG =)(χ 矛盾，故 1)(?≥′ kGκ 。证毕。
推论 6.2.3 设 G 是临界 k-色图，则 1)(?≥ kGδ 。
证明：由定理 )()()( GGG κκδ ≥′≥ 及定理 6.2.2，有 1)()(?≥′≥ kGG κδ 。证毕。
推论 6.2.4 任何 k 色图至少有 k 个顶点的度 1?≥ k 。
证明：设 G 是 k 色图,H 是其一个临界 k 色子图，由推论 6.2.3,H 的每个顶点在 H 中的度
1?≥ k,故在 G 中的度也 1?≥ k 。由于 H 是 k 色临界的，因此它至少有 k 个顶点。证毕。
三、色数的上下界
U
1
U
2
U
k -1
null
S
W
1
W
2
W
k-1
null
S
x
1
x
2
x
k-1
y
2
y
k-1
y
1
null
null
H
8
定理 6.2.3 对任何简单图 G,1)()( +Δ≤ GGχ 。
证明：设 kG =)(χ,且 H 是 G 的临界 k 色子图，由推论 6.2.3,1)(?≥ kHδ 。故
1)(1)()()(?=?≥≥Δ≥Δ GkHHG χδ 。证毕。
定理 6.2.3 给出的上界是可以达到的，例如奇圈和完全图的色数恰好等于它们的最大度加 1。下面来证明，达到这个上界的连通简单图只有这两类图。
定理 6.2.4 (Brooks,1941) 设 G 是连通的简单图，且 G 既不是奇圈又不是完全图，则
)()( GG Δ≤χ 。
证明：设 G 是满足定理条件的 k 色图。
Case1,G 本身是临界 k 色的。
由推论 6.2.1,G 是一个块。又由于临界 1 色图和临界 2 色图是完全图，而临界 3 色图是奇圈，故 4≥k 。由推论 6.2.3,(G) 3δ ≥ 。
如果 G 是 3 连通的,则因 G 不是完全图,故必存在顶点 )(,,GVzyx ∈,使得 )(GExy?,
而 )(,GEyzxz ∈,并且 G{,}x y? 连通。如果 G 的连通度为 2，则 G 中存在一点 z，使得
G{}z? 有割点且连通，此时 G{}z? 至少有两个连通块只含 1 个割点（见第二章习题）,设
B
1
,B
2
为这样两个块。 因 G 本身 2 连通且无割点,故 B
1
,B
2
均有点在 G 中与 z 相邻。 设
1
Bx∈
和
2
By∈ 是两个与 z 相邻的点。由于 x
1
和 x
2
在不同的块中，因此它们在 G{}z? 中不相邻，
因而在 G 中也不相邻，且因 () ( ) 3
G
dz Gδ≥≥,G{,}x y? 连通。
总之，必存在顶点 )(,,GVzyx ∈,使得 )(GExy?,)(,GEyzxz ∈ 且 G{,}x y? 连通。
给 G 的顶点重新编号：首先 yxxx ==
21
,,然后对 },{\ yxGG =′ 中的顶点，按 G′中到 z
的距离由远及近的次序依次用
34
,,,x xx
υ
null 编号，即,),(),(
1
zxdzxd
iGiG +′′
≥,
( 3,4,,i υ= null ),（注意 G′仍连通） 。
因此 x z
υ
=,且对每个 1,2,,1i υ=?null,必存在 ij > 使得 ()
ij
x xEG∈ 。由此可知，
对每个 1,2,,1i υ=?null,
i
x 与 },,,{
121?i
xxx null 中最多 1)(?Δ G 个顶点相邻（因与
i
x 相邻的至少有一个顶点的下标 i> ）,且因 3)()( ≥≥ Gzd δ,故
1
()x xEG
υυ?
∈ 。
这样一来,可用 )(GΔ 种颜色给顶点进行染色,将 x
1
和 x
2
染色 1,然后按颜色 Δ，，,null21
的顺序依次给
34
,,,x xx
υ
null 进行染色，使相邻两点染不同的色。染法为,
设
11
,,
i
xx null 已染好，考虑 x
i
,( 31i υ≤ ≤?)。由于 x
i
仅与
11
,,
i
xx null 中最多 1)(?Δ G
个顶点相邻，所以 Δ，，,null21 种颜色中至少有一种颜色 α 在 },,,{)(
121?ii
xxxxN null∩ 中未
(x
1
)
x
7
x
6
x
5
x
4
x
3
(x
2
)
z
x
9
x
y
x
8x
10
9
曾用过，因此可给点
i
x 染以颜色 α 。因 x
υ
(=z)既与 x
1
又与 x
2
相邻，且 x
1
和 x
2
染的色相同，
所以 Δ 种色中同样也有一种色 β 在 (Nx
υ
)中未曾用过,（因 ()dx
υ
≤ Δ,而 x
υ
的邻点中已有两点染同一种色，故 Δ 种色不会全在 ()Nx
υ
中出现） 。因此可给 x
υ
染以色 β 。
如此便得图 G 的一个正常 Δ -染色，即有,)()( GG Δ≤χ 。
Case2,G 不是 k 色临界的。此时取 G 的一个临界 k 色子图 H。
(1) 若 H 是完全图，则 H＝
k
K,从而
)(1)(1)1()()( GHkkHG Δ≤+Δ=+?=== χχ （ G 中有不属于 H 的边和点） ；
(2) 若 H 是一个奇圈，则 )(3)()( GHG Δ≤== χχ （ G 中至少有一条不属于 H 的边） 。
(3) 若 H 既不是完全图，也不是奇圈，则由 Case1 的证明可知 )()()( GHH Δ≤Δ≤χ,
从而 )()()( GHkG Δ≤== χχ 。
证毕。
例 6.2.1 求 Peterson 图的色数。
解：因 Peterson 图 G 含有奇圈，故不是二部图，因而 3)( ≥Gχ ；
另一方面,G既不是奇圈又不是完全图，且 3)( =Δ G,
故 3)()( =Δ≤ GGχ 。因此,3)( =Gχ 。
虽然奇圈和完全图可以达到定理 6.2.3 提供的色数上界 ()1GΔ +,但某些图类的色数与这个上界相差很远，比如星图
1,
K
n
的色数为 2，
1,
(K ) 1
n
nΔ +=+1。下面给出的几个上界在某种程度上是对定理 6.2.3 的改进。
定理 6.2.5 设连通简单图 G 的度序列为
12
dd d
υ
≥≥≥null,则
(G) 1 max min{,1}
i
i
diχ ≤ +?
证明：将 G 的所有顶点按度的递减（不增）顺序排序，设为
12
,,,vv v
υ
null 。从 v
1
开始依次给顶点染色。在第 i 次染色时，用 v
i
的邻点尚未使用的颜色中色号最小的颜色给 v
i
染色（事先对使用的颜色编号）,(1,2,,)i υ= null 。由于对 v
i
染色时，下标比 i 大的顶点尚未染色，而下标小于 i 的顶点中与 v
i
相邻的顶点不超过 min{,1}
i
di? 个，因此以使用的颜色数也不会超过 min{,1}
i
di?,从而按染色规则，对 v
i
染色使用的颜色编号不会超过 min{,1}
i
di? +1。
时。这个结论对所有 1,2,,i υ= null 都成立。因此将 G 的所有顶点全部染色使用的颜色不会超过 max min{,1} 1
i
i
di? + 种。证毕。
定理 6.2.5 对任何图 G，
HG
(G) 1 max (H)χ δ
≤+ 。
证明：对于空图，结论显然成立。因此可设 (G) 2kχ = ≥ 。
取 G 的一个临界 k 色子图 H
0
，则
0
HG
(H ) max (H)δ δ
≤ 。由推论 6.1.3,
1
1
3
3
2
2
3 1
1
2
10
00
HG
(G) (H ) 1 (H ) 1 max (H)kχ χδ δ
= =≤+ ≤+ 。
证毕。
定理 6.2.6 用 (G)l 表示图 G 中最长路的长度，则 (G) 1 (G)lχ ≤ + 。
证明：结论对于空图显然成立。因此可设 (G) 2kχ = ≥ 。
取 G 的一个临界 k 色子图 H，由推论 6.2.3，则 (H) 1kδ ≥?。用最长路方法不难证明，
H 中有长为 (H)δ 的路。因此 (G)l (H) 1kδ≥≥?。从而 (G) 1 (G)klχ = ≤+ 。证毕。
关于色数的下界有如下定理。
定理 6.2.7 对任何图 G，
2
2
(G) 1
ε
χ
υ
≥+
证明：设 G 的色数是 k，则有 )(GV 的一种划分,),,,(
21 k
VVV null=π,其中 φ=
ji
VV ∩,
)(
1
GVV
k
i
i
=
=
∪
，且每个
i
V 是非空的独立集 ),,2,1( ki null= 。按分组
12
,,,
k
VV Vnull 的次序将 G
的所有顶点依次编号后，其邻接矩阵可写为如下分块形式
11 12 1
21 22 2
12
A(G)
k
k
kk k
AA A
AA A
AA A
=
null
null
nullnullnullnull
null
其中主对角线上每个
ii
A 都是零矩阵。
设 ||
ii
Vp=,则矩阵 A(G)中至少有
2
1
k
i
i
p
=
∑
个零元素。另一方面,A(G)共有
2
υ 个元素但
G 只有 ε 条边。由邻接矩阵的对称性,ε 条边在 A(G) 中形成 2ε 各非零元素，故 A(G)中零元素的个数应为
2
2υ ε? 个。由以上两方面，有
2
2υ ε? ≥
2
1
k
i
i
p
=
∑
。利用柯西不等式
22 2
11 1
()()( )
kk k
ii i
ii i
ab ab
== =
≥
∑∑ ∑
，有 k?
2
1
k
i
i
p
=
∑
≥
22
1
()
k
i
i
p υ
=
=
∑
。从而
2
2υ ε? ≥
2
k
υ
。由此解得
2
2
1k
ε
υ
≥+，即
2
2
(G) 1
ε
χ
υ
≥+
。证毕。
图的色数与独立集和团有关。利用一个图的独立数和团数，可以获得其色数的上下界。
定理 6.2.8 对任何图 G，有（ 1） (G) (G) 1χ αυ+ ≤+,（ 2） (G) (G)χ αυ? ≥ 。 （ (G)α 是
G 的点独立数）
证明,（ 1）设 I 是 G 的一个最大点独立集，则 | I | = (G)α 。给 I 中的点染上一种颜色,G
中其余 (G)υ α? 个顶点每点染一种不同的颜色，这样得到 G 的一个 (G) 1υ α? + 种颜色的正常染色，因此 (G) (G) 1χ υα≤? +。
（ 2） 设 (G) kχ = 。按定义,V(G)可划分为 k 个非空独立集
12
,,,
k
VV Vnull,则
(G) | |
i
Vα ≥,1,2,,ik= null 。从而
1
() | |
k
i
i
kG Vα υ
=
≥=
∑
，即 (G) (G)χ αυ? ≥ 。
11
定理 6.2.9 对任何图 G，有 (G) (G)χ ω≥,(G)ω 是 G 的团数。
证明,设 W 是 G 的一个最大团，因 W 中所有点都在 G 中彼此相邻，因此对 G 染色时 W 的每个点需要一种不同的颜色，故 (G) (G)χ ω≥ 。证毕。
Reed 在 1998 年提出一个猜想
[4]
：图的色数的上界 (G)+1Δ 和下界 (G)ω 的平均值也是色数的一个上界，即
(G) 1 (G)
(G)
2
ω
χ
Δ++
≤
。这个猜想尚未得到证实。
Borodin 和 Kostochka 曾猜想
[5]
，当 (G) 9Δ ≥ 时，如果 (G) (G)ω <Δ,则
(G) (G)χ <Δ 。 1999 年 Reed 证明了在
14
(G) 10Δ≥ 时，上述结论是正确的
[6]
。
[4] B,Reed,,,andω χΔ,J,Graph Theory,27(1998),177-212,
[5] O.V,Borodin,and A.V,Kostochka,On an upper bound of the graph’s chromatic number
depending on the graph’s degree and density,J,Comb,Theory (B),23(1977)247-250,
[6] B.Reed,A strengthening of Brooks’ theorem,J,Comb,Theory(B),76(1999),136-149,
按照定理 6.2.9，一个图有大的团则必有大的色数。直觉上看，反过来也应该成立，即
G 的色数较大则它应该也含有大的团，或者说团数 (G)ω 较小时色数 (G)χ 也会较小。已被部分证实的上述 Borodin-Kostochka 猜想似乎也支持这一说法。但令人惊奇的是，事实并非如此。下一个定理表明，存在 (G)ω =2 但 (G)χ 可以任意大的图。
定理 6.2.10 对任意的正整数 k，存在不含三角形的 k 色图。
证明：对 k=1,2，定理的结论显然成立。下设 3k ≥ 。一个不含三角形的 3 色图是长为 5 的圈 C
5
。下面我们从 C
5
出发递推地由某个不含三角形的 k 色图 G
k
构造不含三角形的 k +1 色图 G
k+1
。构造方法如下：设 G
k
的顶点集为 {
12
,,,
n
uu unull }，给 G
k
添加 n+1 个新顶点
12
,,,,
n
vv vvnull,每个 v
i
与 u
i
在 G
k
中的所有邻点连边，同时也与 v 连边,1,2,,in= null 。例如由 C
5
按上述方法构造出的图如下，该图称为 Gr?tzsch 图。容易检验它是一个无三角形的
4 色图（习题） 。下面证明按这种方法构造出的 G
k+1
都是无三角形的 k+1 色图。
令 V
*
={
12
,,,
n
vv vnull }。假如 G
k+1
中有三角形 C
3
，则 C
3
中必含有 V
*
的点。另一方面，
因 V
*
是独立集，故 C
3
中至多含 V
*
中的一个点，由于 v 仅与 V
*
中点有连边，因此不可能出现在 C
3
上。无妨设 C
3
的顶点是,,
ijt
uu v。按 G
k+1
的构造方法，与除 v
t
相邻的旧顶点一定与
u
t
相邻，这表明,,
ijt
uu u是 G
k
中的一个三角形。这与 G
k
中不含三角形矛盾，因此 G
k+1
中不可能出现三角形。
C
5
u
1
u
3
u
2
u
3
u
5
v
1
v
2
v
3v4
v
5
v
u
1
u
3
u
2
u
3
u
5
Gr?tzsch 图
12
设 (G )
k
kχ =,我们来证明
1
(G ) 1
k
kχ
+
= + 。
首先在 G
k
的正常 k 染色基础上，可得到 G
k+1
的正常 k+1 染色。事实上，由于在 G
k+1
中每个 v
i
与相应的 u
i
不相邻，因此只要给 v
i
染 u
i
原有的颜色（ 1,2,,in= null ）,而给 v 染第
k+1 种颜色，即可将 G
k
中的正常 k 染色扩充为 G
k+1
中的正常 k+1 染色。由此可知
1
(G ) 1
k
kχ
+
≤+。
下面来证明
1
(G ) 1
k
kχ
+
≥+，用反证法。假定
1
(G )
k
kχ
+
≤,则因 G
k+1
的子图 G
k+1
的色数为 k，因此必有
1
(G )
k
kχ
+
= 。设 π 是 G
k+1
的一个正常 k 染色，通过对颜色重新命名，
总可假定 v 染第 k 种色。 由于 v 与所有 v
i
相邻,因此
12
,,,
n
vv vnull 的颜色全在 {1,2,,1k?null }
中。设在当前染色下，顶点
12
,,,
n
uu unull 中染第 k 种颜色的顶点的集合为 V
k
。对
ik
uV?∈，
将其染色改为 ()
i
vπ 。我们来证明经过这种改动后，得到 G
k
的正常 k?1 染色。
事实上,(1) 由于在原来的染色下
k
V 中的顶点染相同的色，因此
k
V 中的顶点互不相邻。
(2) V(G )
kk
V? 中的所有顶点染色未作改变，因此其中相邻的顶点保持不同的色。
(3) 对
ik
uV?∈和 ()
jkk
uVG V?∈?，如果它们相邻，则由 G
k+1
的构造知,u
i
的相应顶点 v
i
也与 u
j
相邻，因此在原有染色中 u
j
与 v
i
染有不同的色，而染色改动后 u
i
的颜色正是 v
i
的颜色,u
j
的颜色未变，可见颜色改动后 u
i
与 u
j
异色。由以上三种情况可知改动后的染色的确是 G
k
的正常 k?1 染色。但这与 G
k
是 k 色图矛盾。
至此，我们已证明了 G
k+1
是无三角形的 k+1 色图。证毕。
该定理中由某个不含三角形的 k 色图 G
k
构造不含三角形的 k +1 色图 G
k+1
的构造方法称为 Mycielski 构造 。
13
§ 6.3 色多项式
本节要考虑的问题是：对于给定的（标定）图 G，用 k 种颜色（ k≥ 1）对 G 进行正常顶点染色，共有多少种不同的染色方式？这里两种染色方式不同，是指至少有一个顶点在这两种染色方式下染有不同的色。
例如，用三种方式给 K
3
染色，不同的染色方式有 6 种。
我们用 P(G,k)表示使用 k 种色对图 G 的顶点正常染色的不同方式数。 P(G,k)是 k 的一个函数，定义域为自然数集。以下将会看到，对一个给定的图 G,P(G,k)是一个关于 k 的多项式。这个多项式称为图 G 的 色多项式（ chromatic polynomial） 。
定理 6.3.1 (1) P(G,k) > 0 的充分必要条件是 ()Gkχ ≤ ；
(2) ()G0ε = （即 G 是空图）时,(,)PGk k
υ
= ;
(3) 若
υ
=GK（即 G 是 υ阶完全图）,则 (,) ( 1) ( 1)PGk kk k υ=+null 。
证明,（ 1） P(G,k)>0 当且仅当 G 至少有一种 k 正常染色，即 ()Gkχ ≤ 。
（ 2） G 是空图则 G 的每个顶点都可以用 k 种颜色中的任一种来染色，故 (,)PGk k
υ
= 。
（ 3） G 是完全图
υ
K,则 G 中第一个顶点有 k 种色可选，第二个顶点有 k?1 种色可选，…，
第 ν 个顶点有 1k υ?+种色可选。故 (,) ( 1) ( 1)PGk kk k υ=+null 。证毕。
设 e 是图 G 的一条边，我们用 G? e 表示边的收缩，即从 G 中删去 e 并将 e 的两个端点粘和在一起后所得的图。
定理 6.3.2 设 G 是简单图，对任意 ()eEG∈,有 (,) (,) (,)PGk PG ek PG ek=。
证明：设 e= uv，考虑用 k 种颜色对 G?e 染色的方式。
（ 1）对 G?e 染色且使 u 与 v 染同色的方式数恰为 P(G? e,k)；
（ 2）对 G?e 染色且使 u 与 v 染异色的方式数恰为 P(G,k)。
因此,(,) (,) (,)PGk PG ek PG ek=。证毕。
利用定理 6.3.2 给出的公式，可以通过减边或增边及边的收缩运算求得一些小阶图的色多项式。
例 6.3.1 求
1,3
K 和
4
C 的色多项式。
=
432
33kkkk?+?,
=
)?(= (
) =
3 ( )? ) + 3 (
1
3 2
v
1
v
2
v
3
3
2 1
v
1
v
2
v
3
2
13
v
1
v
2
v
3
1
23
v
1
v
2
v
3
3
12
v
1
v
2
v
3
2
3 1
v
1
v
2
v
3
14
= (1)(2)(3)2(1)(2)(1)kk k k kk k kk++?
2
(1)( 33)kk k k=+,
定理 6.3.3 设 ()
r
hG表示将 G 的顶点集划分为 r 个非空独立集的划分个数，则
1
(,) [ ( ) ( 1)( 2) ( 1)]
r
r
PGk h Gkk k k r
υ
=
=+
∑
null 。
证明：对每个正整数 r,(1 rk≤≤)，如果 G 不存在正常 r 点染色，则 ()
r
hG=0；如果 G 存在正常 r 点染色（恰使用 r 种颜色）,则 G 的顶点集可划分为 r 个非空独立集
12
,,,
r
VV Vnull 。
现用 k 种颜色给这些独立集染色 ()kr≥,使得每个独立集的顶点染一种色，不同独立集的顶点染不同的色，共有 (1)(2)( 1)kk k k r+null 中染法。每一种染法都给出 G 的一个正常 k 点染色。由于将 G 的顶点集划分为 r 个非空独立集的划分有 ()
r
hG种方式，因此对应于
r个独立集划分的各种可能方式共能得到图 G的 ()
r
hG? (1)(2)( 1)kk k k r+null 种正常
k 点染色。 当 r 从 1 取至 k 时,得到
1
[()( 1)( 2) ( 1)]
k
r
r
hGkk k k r
=
+
∑
null 种正常 k 点染色，
这些点染色显然是不同的正常 k 点染色。由于 G 的每种正常 k 点染色都可看作将 G 的顶点集划分为 k 个独立集（可以有空集）,因此都在上述计数之内。这说明 G 的正常 k 点染色的方式数恰为
1
[()( 1)( 2) ( 1)]
k
r
r
hGkk k k r
=
+
∑
null,即
1
(,) [ ( ) ( 1)( 2) ( 1)]
k
r
r
PGk h Gkk k k r
=
=+
∑
null 。
当 k υ< 且 rk> 时,(1)(2)( 1)kk k k r+null = 0；当 k υ> 且 r υ> 时,()
r
hG= 0。
因此上式与
1
(,) [ ( ) ( 1)( 2) ( 1)]
r
r
PGk h Gkk k k r
υ
=
=+
∑
null 等价。证毕。
我们利用定理 6.3.3 来求 C
4
的色多项式。将 C
4
划分为两个点独立集只有一种方式，即相间隔的两点作为一个独立集，因此
24
()1hC = ；将 C
4
划分为三个点独立集有两种方式：
相间隔的两点作为一个独立集，另两点各自作为独立集，因此
34
()2hC = 。此外，显然
14
()0hC =,
44
()1hC = 。按定理 6.3.3,
2
4
(,)1( 1)2( 1)( 2)1( 1)( 2)( 3) ( 1)( 3 3)PC k kk kk k kk k k kk k k= + + = +,
这与前面计算的结果一致。
定理 6.3.4 对任何简单无环图 G,P(G,k)是 k 的整系数 υ次多项式，且
（ 1）首项为 k
υ； （ 2）第二项为
1
k
υ
ε
； （ 3）常数项为零； （ 4）系数正负交替出现。
证明,对 ε 作归纳。无妨设 G 是简单图。
0ε = 时,(,)PGk k
υ
=,结论成立。
假设 1mε ≤?时结论成立。考虑 mε = 的情形。由归纳假设,
= +) + (++ + + 2) == (
15
2
1
1
(,) (1) (1)
ii
i
i
PG ek k k ak
υ
υυ υ
ε
=
= +?
∑
,
1
(,) (1)
ii
i
i
PG ek k k bk
υ
υυ υ
ε
=
′?=? +?
∑
3
12 1
,
其中 ε′是 G?e 的边数,a
i
,b
i
是非负整数。由定理 6.3.2,
(,) (,) (,)PGk PG ek PG ek=
2
1
1
(1) (1)
ii
i
i
kk ak
υ
υυ υ
ε
=
= +?
∑
1
[()]
ii
i
i
kk bk
υ
υυ υ
ε
=
′ +?
∑
3
12 1
12
2
1
() (1)()
ii
ii
i
kk ak abk
υ
υυ υ υ
υ
εε
=
′=? ++ +? +
∑
3
。
证毕。
下一个定理是显然的。
定理 6.3.5 （ 1）若图 G 有 w 个连通分支 G
1
,G
2
，…,G
w
，则
1
(,) (,)
w
i
i
PGk PG k
=
=
∏
。
（ 2） P(G,k)中系数非零的项的最低次幂为 k
w
，其中 w 是 G 的连通分支数。
定理 6.3.6 G 是树的充分必要条件是 (,) ( 1)PGk kk
υ?
=?
1
。
证明,充分性。 设 (,) ( 1)PGk kk
υ?
=?
1
,则色多项式的最低次幂是 k 的 1 次项。 由定理 6.3.5
知,w=1，即 G 是连通图；又因 (1)kk
υ?
1
的 υ?1次项的系数是 ()υ1,故 ε υ=?1。
因此 G 是树。
必要性。设 G 是树。下面对 G 的顶点数 υ用归纳法来证明 (,) ( 1)PGk kk
υ?
=?
1
。
当 υ = 1时，显然 P(G,k) = k，结论成立。
假设对 1nυ ≤?的所有树，结论成立。
对 nυ = 的任何树 G，取 G 的一个叶顶点 v
0
，令 G′= G? v
0
，则由归纳假设,
()-1 ()2
(,) ( 1) ( 1)
GG
PG k kk kk
υυ′?
′ =? =? 。
注意对 G′的每一个点正常 k 染色,v
0
有 k?1 种染色法使 G 正常染色，故
()
(,) (,)( 1) ( 1)
G
PGk PG k k kk
υ?
′=?=?
1
。
定理 6.3.7 设 G 是圈，则 (,) ( 1) ( 1) ( 1)PGk k k
υυ
=?+。
证明,对 G 的顶点数 υ作归纳。
υ = 3时,G 是完全图 K
3
，故 P(G,k) = k(k? 1)( k?2 ) = ( k? 1)
3
+ (?1)
3
( k? 1)。
假设对 nυ = 的所有圈，定理结论都成立。考虑顶点数 () nυ = +G1的圈 G。
从 G 中任取一条边 e，显然 G?e 是一个 n+1 阶树。 由定理 6.3.6,
11
(,)(1) (1)
nn
PG ek kk kk
+?
=? =?。
此外,G?e 是 n 阶圈，由归纳假设,(,) ( 1) ( 1) ( 1)
nn
PG ek k k? =?+。 再由定理 6.3.2,
16
(,) (,) (,)PGk PG ek PG ek= (1)
n
kk=? [( 1) ( 1) ( 1)]
nn
kk+
= (1) (1)(1)
11nn
kk
++
+ = (1)(1)(1)kk
υυ
+ 。
证毕。
本节最后，我们列举关于色多项式的几个未解决的问题。
1,色多项式与图不是一一对应的。虽然同构的图有相同的色多项式，但色多项式相同的两个图未必同构。例如，所有 υ个顶点的树都有相同的色多项式，但并非所有 υ阶树都是同构的。
问题 1,有相同色多项式的图有什么共同特点？
2,满足定理 6.3.4 的多项式未必就是色多项式。 例如,多项式
432
33kkk?+满足定理 6.3.4，
但它不是任何图的色多项式。事实上，假如它是某个图 G 的色多项式，则
（ 1）若 G 连通，因,ε υ==34，故 G 应是一个树，其色多项式应为
34 3 2
(1) (1) 3 3kk kk k k k
υ?
=?≠?+
1
。
（ 2）若 G 不连通，则因它有 4 个顶点 3 条边，故只能是
31
GK K= ∪ 。而此时
432
31
(,) (,) (,) ( 1)( 2) 3 3PGk PK k PK k kk k k k k k=?=≠?+。
问题 2,如何判断一个多项式是色多项式？
3,Read 猜想：色多项式 P(G,k)的系数的绝对值总是先严格单调递增，然后严格单调递减。
问题 3,证明或否定这一猜想。
4,问题 4,设计求色多项式的更好的算法。
注,求图的色多项式的有效算法将给出求图的点色数的有效算法，因此，确定图的色多项式的问题是一个 NPC 问题。
有关色多项式的更多内容可参看 [7],[8],[ 9]或 [10]。
[7] D.B,West,Introduction to Graph Theory (second edition),Prentice-Hall,Inc.,2001,（中译本：李建中、骆吉周译，图论导引，机械工业出版社,2006） 。
[8] W.T,Tutte,Graph Theory,Cambridge University Press,2001,
[9] R.C,Read and W.T,Tutte,Chromatic polynomials,Selected Topics in Graph Theory 3,
(eds,L,W,Beineke,and R.J,Wilson),Academic Press,New York,(1988) 15-42,
[10] D,Reinhard,Graph Theory (second edition),Springer-Verlag New York,2000,
17
§ 6.4 完美图
在 6.2 节，我们得到色数的一个下界,(G) (G)χ ω≥,其中 (G)ω 表示图 G 的团数。
有一些图的色数能达到这个下界，比如完全图和二部图。如果一个图的任何导出子图的色数都能达到这种下界，则称这个图为完美图。完美图的正式定义如下。
定义 6.4.1 若图 G 的每个点导出子图 H 都有 (H) (H)χ ω=,则称 G 为 完美图 。
容易验证，完全图及完全图的补图（空图）都是完美图。
定理 6.4.1 （ 1） 2n ≥ 时，偶圈
2n
C 及其补图都是完美图；
（ 2） 2n ≥ 时，奇圈
21n
C
+
及其补图都不是完美图；
证明,（ 1） 2n ≥ 时，偶圈
2n
C 的色数和团数都是 2。而且,C
2n
除自身外的任何导出子图 H
是一些路的不交并（可能会有孤立顶点） 。如果 H 不全是孤立顶点，则其色数和团数都是 2；
如果全是孤立顶点，则色数和团数都是 1。因此
2n
C 是完美图。
对
2n
C 的补图
2n
C,因其中任何 3 点都不是独立集，对其顶点正常染色时每个色类（染同一色的顶点集合） 不超过 2 个顶点,因此
2n
C 的顶点正常染色至少需要 n 种色。 另一方面，
设沿着圈
2n
C 顶点依次为
12 2
,,,
n
vv vnull,
2n
C 中对
12
,vv染同一种色，
34
,vv染同一种色，…，
21 2
,
nn
vv
染同一种色，则获得
2n
C 的一种顶点正常 n 染色，可见
2
()
n
Cnχ = 。其次，所有奇数下标的点在
2n
C 中彼此互不相邻,从而构成
2n
C 的一个 n 点团。 因此
22
() ()
nn
CnCωχ≥= 。
另一方面，由色数的下界
22
() ()
nn
CCχω≥,便知
22
() ()
nn
CCχω= 。
对
2n
C 的任一个异于
2n
C 的导出子图 H，设其顶点下标（按
2n
C 上的标号）由小到大依次为
12
,,,,
k
ii i
vv vnull ( 2kn< ),这些顶点在
2n
C 上导出的子图 H′是一些路及一些孤立顶点的不交并。设这些路中有 r
1
条含有偶数个顶点,r
2
条含有奇数个顶点，另有 r
3
个孤立顶点。
对每条路，取其一个端点作为起始点，依次对路上的点交替标上奇偶标号。并从起始边开始间隔取边作为匹配边,这样可得到 H′的一个最大匹配。 设该最大匹配有 r 对点 （即 r 条边）,
则这 r 对顶点的每一对在 H 中互不相邻，可染同一种色。又因 H 中任何三点都不构成独立集，故 (H) ( 2 )rk rkrχ =+? =?。另一方面，取上述各条路上所有奇标号的顶点，与 H′的所有孤立点组成顶点子集 A，则 A 是 H′的最大独立集，从而是 HH′= 的最大团。因为在含有偶数个顶点的路上，奇标号顶点的个数与匹配边的个数相等，而在每条含有奇数个顶点的路上，奇标号顶点的个数比匹配边的个数多 1，因此 |A| = r + r
2
+ r
3
。因 r
2
+ r
3
是各条含有奇数个顶点的路上未被匹配的点数与 H′中孤立顶点个数之和，故 r
2
+ r
3
= k? 2r。从 而 |A| =
r + (k?2r) = k? r。由此可见 (H) | A | (H)krω χ= =?= 。因此
2n
C 是完美图。
18
（ 2） 2n ≥ 时，奇圈
21n
C
+
的色数是 3，团数是 2，因此不是完美图。
对
21n
C
+
的补图
21n
C
+
,因其中任何 3 点都不是独立集,对其顶点正常染色时每个色类 （染同一色的顶点集合）不超过 2 个顶点，因此
21n
C
+
的顶点正常染色至少需要 n+1 种色。另一方面，设沿着圈
21n
C
+
顶点依次为
12 21
,,,
n
vv v
+
null,
21n
C
+
中对
12
,vv染同一种色，
34
,vv染同一种色，…，
21 2
,
nn
vv
染同一种色，最后给
21n
v
+
染一种色，则获得
21n
C
+
的一种顶点正常
n+1 染色，可见
21
() 1
n
Cnχ
+
=+。其次，考虑
21n
C
+
的最大团。因
i
v 与
1i
v
+
在
21n
C
+
中不相邻
（ 1,2,,2in= null ）,且
21n
v
+
与 v
1
也不相邻，故从
12 21
,,,
n
vv v
+
null 中最多能取出 n 个在
21n
C
+
中彼此相邻的点,即
21n
C
+
的最大团含点数不超过 n 个。 因此
21 21
() 1()
nn
Cnn Cωχ
++
≤<+= 。
这表明
21n
C
+
不是完美图。
定理 6.4.2 任何二部图及二部图的补图都是完美图。
证明：因为二部图的色数和团数都为 2，且其任何一个导出子图仍为二部图，故二部图都是完美图。下证二部图的补图是完美图。
设 G 是一个二部图，对补图 G 的任一个子图 G′，它必定是 G 的某个子图 H 的补图，
即 HG，使 GH′= 。下面只需证明 (H)= (H)χω即可。
用 (H)α 和 (H)β′ 分别表示 H 的独立数和边覆盖数，则 (H)= (H)ωα，且由推论 5.2.2，
(H)= (H)α β′ 。另一方面，设 (H) kχ =,{
12
,,,
k
VV Vnull }是 H 的一个顶点正常 k 染色，则每个
i
V 是 H 的一个团。由于二部图 H 中无三角形,H 的团要么只有１个点，要么只有两个点。因此，各个
i
V 在 H 中的导出子图合在一起形成了 H 的一个匹配 M 和一些 M 未饱和点。
由于 {
12
,,,
k
VV Vnull }是 H 的顶点正常染色的最小色类划分，故 M 是 H 的最大匹配。由推论
5.2.1,(H)=|M|+β′ M 未饱和点的个数＝ k。
因此,(H)= (H)= (H) (H)kωαβ χ′ == 。证毕。
设 G 是一个图。 G 的 线图 (line graph)L(G)是以 G 的边集作为顶点集的图,L(G)中两顶点相邻当且仅当相应的两条边在 G 中相邻。
线图的性质已得到较好的研究，读者可参看 [11]或 [12]
[11] F,Harary,Graph Theory,Addison-Wesley,Reading,Mass.,1969.(中译本,李慰萱译,图论，
上海科技出版社,1980),
[12] R.L,Hemminger,and L,W,Beineke,Line graphs and line digraphs,Selected Topics in Graph
Theory (L,W,Beineke,and R.J,Wilson editors),Academic Press,London,(1983),271-306,
值得注意的是,G 的线图 L(G)中的一个团与 G 中的一个顶点及其关联边对应，该团含的顶点数等于 G 中对应顶点的度。 L(G)中的一个独立集与 G 中的一个匹配相对应,L(G)的独立数等于 G 的边覆盖数（即最大匹配所含的边数） 。 L(G)的点正常染色对应于 G 的边正常染色，故 (L(G)) (G)χ χ′= 。
19
定理 6.4.3 设 G 是二部图，则 G 的线图 L(G)及其补图 L(G) 都是完美图。
证明：因 (L(G))ω 等于 G 的顶点最大度 (G)Δ,而 (L(G)) (G)χ χ′= 。 G 是二部图，由定理 6.1.1,(G) (G)χ′ =Δ,从而 (L(G)) (L(G))χ ω= 。由于 L(G)的点导出子图对应于 G
的边导出子图，而二部图的边导出子图仍是二部图，故上述推导对 L(G)的所有点导出子图都成立，因此 L(G)是完美图。
下面考虑线图 L(G)的补图 L(G) 的完美性。设 (L(G)) kχ =,
12
{,,}
k
VV Vnull 是 L(G) 的一个顶点 k 正常染色。每个
i
V 是 L(G) 的一个独立集，即 L(G)的一个团，它对应于 G 中某个顶点（记为 v
i
）关联的所有边
i
E,(1,2,,)ik= null 。因
12
(( ))
k
VV VVLG=∪∪null∪,故
12
EE EE()
k
G=∪∪null∪,这表明
12
{,,,}
k
vv vnull 是 G 的一个点覆盖集，而且 (L(G)) kχ =
保证了它是 G 的一个最小点覆盖，因此,(L(G)) (G)kχβ== 。另一方面,(L(G))ω 等于 L(G) 中最大点独立集含的顶点数，进而等于 G 中最大匹配所含的边数，即
(L(G))ω (G)α′= 。 由 K?nig-Egerváry 定理 （定理 5.2.2）,对于二部图 G,有 )()( GG βα =′,
因此 (L(G))χ = (L(G))ω 。因 L(G) 的点导出子图必是 L(G)的相应点导出子图的补图，它对应于 G 的一个边导出子图，而二部图的边导出子图仍是二部图，故上述推导对 L(G) 的所有点导出子图都成立，因此 L(G) 是完美图。证毕。
以上完美图和非完美图的个例都支持一个普遍性的命题,一个图是完美图当且仅当它的补图是完美图。这个命题称为 完美图猜想,由 Berge 于 1961 年提出。许多人认为要证明这个猜想是很困难的。 1972 年,22 岁的 Lovász 证明了这个著名的猜想，在当时引起了组合数学界的轰动。下面我们来介绍对完美图猜想的证明。
引理 1 图 G 是完美图当且仅当对 G 的每个点导出子图 H，存在一个独立集 I，使得
(H I) (H)ω ω?< 。即 G 是完美图当且仅当 G 的每个点导出子图 H 都有一个独立集 I，它与 H 的所有最大团都有公共顶点。
证明：必要性。设 G 是完美图,H 是 G 的一个点导出子图，则 (H) (H)χ ω= 。设
(H) kχ = 。在 H 的任何一种顶点 k 正常染色下，设 I 是一个色类（染某种色的所有顶点之集） 。则有
(H I) (H I) 1 (H) 1 (H) 1 (H)kω χχωω? ≤?=?=?=?< 。
充分性：对 (G)ω 作归纳法。
当 (G)ω =1 时,G 显然是完美图。
假定对满足定理条件且 (G) kω < 的任何图 G,G 都是完美图。
设 G 是一个使得 (G) kω = 的图，且对 G 的每个点导出子图 H，存在一个独立集 I，使得 (H I) (H)ω ω?< 。由归纳假设,HI? 是完美图，于是 (H I) (H I)χ ω? =?。设
(H I) rχ?=且
12
{,,,}
r
VV Vnull 是 HI? 的一个顶点正常 r 染色。则
12
{,,,,I}
r
VV Vnull 是 H 的一个顶点正常 r+1 染色。故 (H) 1 (H I) 1 (H I) 1 (H)rχ χωω≤ +=? +=? +≤ 。另一方面,(H) (H)χ ω≥ 。因此 (H) (H)χ ω= 。这表明 G 是完美图。归纳完成。证毕。
20
设 G 是一个图，其顶点集为
12
{,,,}
n
vv vnull,
12
H,H,,H
n
null 是一些无公共顶点的图。
将 G 中每个顶点
i
v 用
i
H 替换 (1,2,,)in= null,并按 G 中顶点的相邻关系连接
12
H,H,,H
n
null,如果
i
v 与
j
v 在 G 中相邻，则将 H
i
的顶点与 H
j
的顶点之间建立完全连接。
这样得到的图称为
12
H,H,,H
n
null 在 G 上的 合成图,记为 G{
12
H,H,,H
n
null }。确切地说，
G{
12
H,H,,H
n
null }的顶点集为
12
V(H ) V(H ) V(H )
n
∪∪null∪,对 G{
12
H,H,,H
n
null }中任意两顶点 u,v，当且仅当 u 和 v 在某个 H
i
中相邻，或者 u 和 v 分别属于 H
i
和 H
j
且相应的
i
v 和
j
v 在 G 中相邻时,u,v 在 G{
12
H,H,,H
n
null }中相邻。
引理 2,若 G 和
12
H,H,,H
n
null 都是完美图，则合成图 G{
12
H,H,,H
n
null }也是完美图。
证明,由于合成 G{
12
H,H,,H
n
null }可以看成是用
12
H,H,,H
n
null 逐次替换
12
,,,
n
vv vnull
得到的，因此只需证明用一个完美图 H 替换 G 的某一个顶点 v 得到的图 G{H} 是完美图即可。按照引理 1，完美图 H 有一个点独立集 I 使得 (H I) (H)ω ω? < 。用 (G)χ 种颜色对 G
的顶点进行正常染色，将 v 及与 v 同色的顶点的集合记为 A，则 B(IA){}v=?∪ 是 G{H}
的一个独立集。我们断言 B 与 G{H}的每个最大团都有公共顶点。
事实上，设 Q 是 G{H}的一个最大团。如果 Q 含有 H 中的顶点，则因在 G{H}中 H 的各个顶点对 H 外的相邻关系是相同的，故此时 H 中每个顶点都与 QH? 的所有顶点相邻。
因此 Q 必定含有 H 的一个最大团。又因 (H I) (H)ω ω? <,H 的每个最大团都与 I 有公共顶点，从而 Q 必定与 I 有公共顶点，于是 B(IA){}v=?∪ 与最大团 Q 有公共顶点。
如果 G{H}的最大团 Q 不含有 H 中的顶点,则 QV(G){}v且在 G 中 v 不与 Q 的顶点相邻，因此 Q 是 G 的一个最大团。因 G 是完美图,(G) (G)χ ω=,且对 G 的任何一种
(G)χ 正常染色，每个色类（同色顶点之集）至多含最大团 Q 中一个点，而
|Q| (G) (G)ω χ==，于是每个色类恰含 Q 中一个点。 因此在 G 的任何一种 (G)χ 正常染色下,Q 与每个色类都有公共点。特别地,Q 与前述色类 A 有公共点，从而与 IA∪ 由公共点，又因为 Q 不含顶点 v，故 Q 与集合 B(IA){}v=?∪ 有公共点。
对 G{H}的任一个点导出子图 G′，如果 GG′? 或 GH′?,则因完美图的子图仍是完美图，故由引理 1,G′有一个独立集，它与 G′的所有最大团都有公共顶点。否则,G′可视为由 G 的某个含 v 的点导出子图与 H 的某个点导出子图在 v 点合成的图，按上述推导,G′
也存在独立集，它与 G′的所有最大团都有公共顶点。
由以上结果可见，图 G{H}满足引理 1 的条件，故是完美图。证毕。
定理 6.4.4 (完美图定理,Lovász
[13],[14]
,Fulkerson
[15]
,1971) 一个图是完美图当且仅当它的补图是完美图。
[13] L,Lovász,Normal hypergraphs and the perfect graph conjecture,Discrete Mathematics,
2(1972),253-267,
[14] L,Lovász,A characterization of perfect graphs,J,Comb,Theory (B),13(1972),95-98,
[15] D.R,Fulkerson,Blocking and anti-blocking pairs of polyhedra,Math,Programming,1(1971),
168-194,
21
证明,必要性,设 G 是完美图。为证其补图 G 也是完美图，由引理 1，只需证明对 G 的任何点导出子图 H,都有一个独立集 I，使 得 (H I) (H)ωω?< 。将 H 的补图记为 H，它 是 H
的顶点在 G 中的导出子图。从 H 的角度来看，需要证明的就是，存在 H 的一个团 Q，使得
(H Q) (H)α α?< 。我们用反证法来证明这一结论。
设 H 的顶点集为
12
{,,,}vv v
υ
null,
12
Q,Q,,Q
r
null 是 H 的全部团。假定对每个 Q
i
，都存在 HQ
i
的某个点独立集
i
A,使得 || (H)
i
A α=,( 1,2,,ir= null )。 对 H 的任一个顶点 v
k
,设
12
,,,
r
AA Anull 中有
k
n 个含有 v
k
，用
k
n 阶完全图
k
n
K 替代 H 中的顶点 v
k
,（ 1,2,,k υ= null ）,
则得到合成图 G′=H{
12
,,,
nn n
KK K
υ
null }。由于完美图 G 的子图 H 是完美图，完全图也是完美图，按照引理 2,G′是完美图。下面来计算 (G )ω ′ 和 (G )χ ′ 。
G′的最大团必可由 H 的某个团 Q
j
的顶点用相应的完全图替代后获得，因此，
j
(G )
k
k
vQ
nω
∈
′ =
∑
。注意
k
n 是 r 个独立集
12
,,,
r
AA Anull 含有顶点
k
v 的独立集的个数。对
1,2,,ir= null,因 A
i
是独立集而 Q
j
是团，故每个 A
i
至多含有 Q
j
中一个顶点。也就是说，对
Q
j
中任何两个顶点
k
v
′
和
k
v
′′
,这 r 个独立集中含有
k
v
′
的独立集和含有
k
v
′′
的独立集互不相同。
此外，与 Q
j
对应的独立集 A
j
不含有 Q
j
中任何顶点。因此，含有 Q
j
中各个顶点的独立集个数之和不会大于 1r?,即
(G )
ki
k
vQ
nω
∈
′ =
∑
1r≤? 。 (1)
另一方面，设 (G ) tχ ′ =,
12
,,,
t
VV Vnull 是 G′的一个顶点 t 正常染色，则
12
(G ) | | | | | | (G ) (G )
t
VV Vυ χα′′′=+ ++≤?null 。 (2)
由 G′的构造可知,(G ) (G)α α′ = 。 (3)
且由
12
,,,
r
AA Anull 的性质，有
1
|| (G)
r
i
i
Arα
=
=?
∑
。 (4)
构造矩阵 M ()
ij
m=,其中
ij
m 当 A
i
含有 H 的顶点 v
j
时取值为 1,否则取值为 0,( 12ir= null，，；
1,2,,( )j Hυ= null ),注意到
1
||
r
i
i
A
=
∑
等于将矩阵 M 的元素按行相加，而将 M 的元素按列相加的结果等于
()
1
()
H
j
j
nG
υ
υ
=
′=
∑
。因此，
1
|| (G)
r
i
i
A υ
=
′=
∑
。结合 (2),(3),(4)式有,
(G ) (G ) (G )χ αυ′′ ′?≥
1
|| (G) (G)
r
i
i
Ar rαα
=
′==?=?
∑
。
即 (G ) rχ ′ ≥,与 (1)式结合，得 (G ) (G )χ ω′ ′> 。这与 G′的完美性矛盾。必要性得证。
充分性,设 G 是完美图，则因 G 是 G 的补图，故由必要性的证明，知 G 也是完美图。
证毕。
在历史上，人们曾定义了两种完美图。为了给出第二种完美图的定义，我们需要引入团覆盖集的概念。
22
设 G 是一个图,F
12
{,,,}
r
QQ Q= null 是 G 的一些团的集合，如果
12
()
r
QQ QVG=∪∪null∪,则称 F 是 G 的一个 团覆盖集 。 G 的含团数最少的团覆盖集称为最小团覆盖集，它所含的团的个数称为 G 的 团覆盖数,记为 (G)θ 。
设 F
12
{,,,}
r
QQ Q= null 是简单图 G 的任一个团覆盖,I 是 G 的任一个点独立集。因 F 是团覆盖，对 I 的任意一点 v,必存在某个团
i
Q,使
i
vQ∈,而 I 中任意两点不会属于同一个团，因此 |I| |F|r≤=,由此可知 (G)θ (G)α≥ 。
定义 6.4.2 若图 G 的每个点导出子图 H 都有 (H) (H)α θ=,则称 G 为关于点独立数的完美图，简称为 α -完美图 。
相应地，我们将定义 6.4.1 中的完美图称为关于色数的完美图，简称为 χ -完美图。下面的定理表明这两种完美图的定义本质上是相同的。
定理 6.4.5 图 G 是 α -完美图当且仅当它是 χ -完美图。
证明：首先证明 G 是 α -完美图当且仅当其补图 G 是 χ -完美图。
事实上,G 的每个点导出子图 H 必是 G 的某个点导出子图 H 的补图 。若 G 是 α -完美图，则 G 有 (H) (H)α θ= 。设 (H) kχ =,
12
,,,
k
VV Vnull 是 H 的一个顶点 k 正常染色，
则
12
,,,
k
VV Vnull 构成 H 的一个最小团覆盖。因此 (H) (H)χθ= 。此外,H 的最大独立集必为 H 的最大团，故 (H) (H)αω= 。从而 (H) (H) (H) (H)χθαω===。这表明 G 是 χ -
完美图。
反之，若 G 的补图 G 是 χ -完美图，则对 G 的任一个点导出子图 H,(H) (H)χω= 。
与前面完全同样的道理，得 (H) (H)χθ= 及 (H) (H)αω= 。因此,
(H) (H)αω= (H) (H)χθ==。
这表明 G 是 α -完美图。
其次，由完美图定理（定理 6.4.4）,G 是 χ -完美图当且仅当 G 是 χ -完美图。从而定理得证。
目前，人们已经发现近百种完美图
[16]
。其中除了前面介绍的一些外，还有区间图和弦图也是较常见的两种。
[16] http://www.cs.rytgers.edu/~chvatal/perfect/spgt.html
设
12
,,
n
JJ Jnull 是 n 个实数区间,以 {
12
,,
n
JJ Jnull }为顶点集构造图 G,G 中顶点
i
J 与
j
J
相邻当且仅当区间
i
J 与
j
J 相交。这样得到的图称为 区间图 (interval graph)。
设 C 是一个圈,C 的一条 弦 是本身不在 C 上但两端点在 C 上的边。如果图 G 中每个长至少为 4 的圈都有弦，则称 G 为 弦图 （ chordal graph） 。
23
定理 6.4.6 区间图是完美图。
证明,设 G 是一个区间图，按 G 的顶点对应区间的左端点值由小到大对 G 的所有顶点排序，设顺序为
12
,,,vv v
υ
null 。依次对 G 的顶点染色：对顶点
i
v,用此前
i
v 的邻点尚未使用的最小色号的颜色给
i
v 染色,（ 1,2,,i υ= null ） 。这样可得到 G 的一个顶点正常染色。设这样染色后用到的最大色号为 k，假定顶点
j
v 染有颜色 k，这说明在给
j
v 染色时，已经至少有
j
v
的 k?1 个下标小于 j 的邻点分别染有颜色 1 到 k?1。设
j
v 对应的区间
j
J 的左端点为 x，则上述 k?1 个顶点对应的区间都与
j
J 相交且左端点小于和等于 x，因而这些区间必定彼此相交。
由此可知这 k 个顶点构成 G 的一个 k-团。从而 (G) (G)kχ ω≤ ≤ 。另一方面，对任何图都有 (G) (G)χ ω≥,故 (G) (G)χ ω= 。
由于区间图 G 的点导出子图 H 仍是区间图,故对 H 上述推导仍成立。 因此 G 是完美图。
证毕。
与定理 6.4.6 类似可证，弦图也是完美图（见 [7] p181） 。
含有奇圈的无三角形图，由于其团数为 2，色数至少是 3，故不是完美图。按照完美图定理，这样的图的补图也不是完美图。这就是说，若 G 是完美图，则 G 和 G 的任何导出子图必定不含有长至少是 5 的奇圈。 Berge 猜想，这个命题的逆命题也是成立的，这便是著名的强完美图猜想。
强完美图猜想 （ Berge
[17]
,1961） G 是完美图当且仅当 G 和 G 的任何导出子图都不是长至少为 5 的奇圈。
[17] C,Berge,F?rbung von Graphen deren s?mtliche bzw,Deren ungerade Kreise starr sind
(Zusammenfassung),Wissenschaftliche Zeitschrift,Martin Luther Universit?t Halle-Wittenberg，
Mathematisch-Naturwissenschaftliche Reihe,(1961),114-115,
经过人们四十年的努力，强完美图猜想终于在 2002 年被 Chudnovsky 等人所证明
[16][18][19]
。此外，判别一个图是否为完美图的多项式时间算法也已被得到
[20],[21]
。这是完美图理论的重大进展。通过围绕完美图猜想和强完美图猜想的研究，完美图理论已经形成了十分丰富的内容，加深了人们对图的结构性质的认识。目前这一领域的研究仍很活跃。
有关完美图的更多内容可参看文献 [7],[16]或 [22]~[27]。
关于染色问题可进一步参考文献 [28]~[64]。
[18] M,Chudnovsky,N,Robertson,P,Seymour,R,Thomas,Progress on perfect graphs,
Mathematical Programming Ser.B,97(2003)405-422,
[19] M,Chudnovsky,N,Robertson,P,Seymour,R,Thomas,The strong perfect graph theorem,
Annals of Mathematics,164:1(2006) 51-229,
[20] M,Chudnovsky,G,Cornuéjols,X,Liu,P,Seymour,K,Vu?kovi?,,Recognizing Berge graphs,
Combinatorica,25(2005),143-186,
[21] G,Cornuéjols,X,Liu,and K,Vu?kovi?,A polynomial algorithm for recognizing perfect
24
graphs,Proceeding of 44
th
FOCS (2003) 20-27,
[22] M.C,Golumbic,Algorithmic Graph Theory and Perfect Graphs,Academic Press,1980
[23] L,Lovász,Perfect graphs,in Selected Topics in Graph Theory II (L.W,Beineke,and R.J,
Wilson eds.),Academic Press,London,(1983),55-87,
[24] C,Berge,and V,Chvátal,Topics on Perfect Graphs,Ann,Discr,Math,21,North Holland,
1984,
[25]A,Schrijver,Combinatorial Optimization Polyhedra and Efficiency,New York,NY,
Springer-Verlag,2003,
[26] J.L,Ramírez Alfonsín,and B.A,Reed,Perfect graphs,J,Wiley and Sons,Chichester,2001,
[27] G,Cornuéjols,The strong perfect graph conjecture,Proceedings of the ICM,Beijing,China,
2002,
[28] Tommy R,Jensen and Bjarne Toft,Graph Coloring Problems,Wiley-Interscience,New York,
1995,
[29] B,Toft,75 graph-colouring problems,in Graph Colourings (R,Nelson and R.J,Wilson,Eds.),
Wiley,New York,(1990),9-35,
[30] http://www.nada.kth.se/~viggo/problemlist/
[31] http://web.cs.ualberta.ca/~joe/Coloring/#Links.other
[32] N,Alon,Restricted colorings of graphs,in Surveys in Combinatorics 1993 (Proc,14
th
British
Combinatorial Conference),Cambridge Univ,Press,Cambridge,(1993),1-33,
[33] H.R,Hind,Restricted Edge-Colourings,Ph.D,thesis,University of Cambridge,1988,
[34] Reinhard Diestel,Graph Theory,Springer,1997,
[35] N,Rorbertson,P,D,Seymour and R,Thomas,Tutte’s edge-coloring conjecture,J,Combin,
Theory Ser,B,70(1997),166-183,
[36] M,O,Albertson,A,V,Kostochka,and D,B,West,Precoloring Extensions of Brooks'
Theorem,SIAM J,Discrete Math.,18(2004-2005),542-553,
[37] L.D,Andersen,On edge-colourings of graphs,Math,Scand,40(1977),161-175,
[38] J,Janssen and K,Kilakos,Bounded Stable Sets,Polytopes and Colorings,SIAM J,Discrete
Math.,12(1999),262-275,
[39] N,Alon and M,Krivelevich,Testing k-colorability,SIAM J,Discrete Math.,15(2001-2002),
211-227,
[40] J,Fiala,K,Jansen,V,B,Le,and E,Seidel,Graph Subcolorings,Complexity and Algorithms,
SIAM J,Discrete Math.,16(2002-2003),635-650,
[41] 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) 361-376,
[42] D,Král',Coloring Powers of Chordal Graphs,SIAM J,Discrete Math.,18(2004-2005),
451-461,
[43] G,Agnarsson and M,M,Halldórsson,Coloring Powers of Planar Graphs,SIAM J,Discrete
Math.,16(2002-2003),651-662,
[44] Cécile Murat and Vangelis Th,Paschos,On the probabilistic minimum coloring and
25
minimum k-coloring,Discrete Applied Mathematics,154(2006),564-586,
[45] G,Chartrand,L,Nebesky and P,Zhang,Hamiltonian colorings of graphs,Discrete Applied
Mathematics,146(2005),257-272
[46] V,Guruswami and S,Khanna,On the Hardness of 4-Coloring a 3-Colorable Graph,SIAM J,
Discrete Math.,18(2004-2005),30-40,
[47] 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),385-411,
[48] H,Enomoto,M,Hornák,and S,Jendrol',Cyclic Chromatic Number of 3-Connected Plane
Graphs,SIAM J,Discrete Math.,14(2001),121-137,
[49] Oleg V,Borodin and Douglas R,Woodall,Cyclic Colorings of 3-Polytopes with Large
Maximum Face Size,SIAM J,Discrete Math.,15(2001-2002),143-154,
[50] V,A,Bojarshinov,Edge and total coloring of interval graphs,Discrete Applied Mathematics,
114(2001),23-28,
[51] O.V,Borodin,On the total coloring of planar graphs,J,Reine Angew,Math.,394(1989),
180-185,
[52] 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),17-20,
[53] Celina M.H,de Figueiredo,J,Meidanis,C,P,De Mello,Total-Chromatic number and
chromatic index of dually chordal graphs,Information Processing Letters,70(1999),147-152,
[54] A,Daneshgar and H,Hajiabolhassan,Unique list-colourability and the fixing chromatic
number of graphs,Discrete Applied Mathematics,152(2005),123-138
[55] O.V,Borodin and A.V,Kostochka,List edge and list total colorings of multigraphs,Journal
of Combinatorial Theory,(Ser,B),71(1997),184-204,
[56] F,Galvin,The list chromatic index of a bipartite multigraph,Journal of Combinatorial
Theory,(Ser,B),63(1995),153-158,
[57] J,Kahn,Asymptotically good list-colorings,J,Combin,Theory Ser,A,73(1996),1-59,
[58] M,R,Salavatipour,On sum coloring of graphs,Discrete Applied Mathematics,127(2003),
477-488,
[59] M,Larsen,J,Propp,and D,Ullman,The fractional chromatic number of Mycielski’s graphs,
J,Graph,Theory,19(1995),411-416,
[60] U,Feige,M,Langberg,and G,Schechtman,Graphs with Tiny Vector Chromatic Numbers
and Huge Chromatic Numbers,SIAM J,Computing,33(2003-2004),1338-1368
[61] S,Gerke,Weighted colouring and channel assignment,DPhil thesis,University of Oxford,
2000,
[62] C,Mcdiarmid,and B,Reed,Channel assignment and weighted colouring,Networks,36(2000)
114-117,
[63] C,Nomikos,A,Pagourtzis and S,Zachos,Routing and path multicoloring,Information
Processing Letters,80(2001) 249-256,
[64] 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),1040-1049,
26
第六章习题
1,证明 n ≠ 0 时,(1)
21
(K )
n
χ
+
′ =2n+1=
21
()
n
K
+
Δ ； (2)
2
()
n
Kχ′ =2n－ 1=
2
()
n
KΔ 。
2,找出一个适当的边染色以证明 )()(
,,nmnm
KK Δ=′χ 。
3,轮图
1,n
W 是由一个点与长为 n 的圈上所有顶点相连形成的图，证明：若 n ≥4，则
1,1,
() ()
nn
WWχ′ =Δ = n。
4．证明：对 Petersen 图 G,(G) 4χ′ = 。
5,（ 1）证明：对于最大度为 Δ 的任何二部图 G，存在着包含 G 的 Δ 正则简单二部图。
（ 2）若 G 是最大度为 Δ 的无环图，则存在 Δ 正则图以 G 为子图。
6．试用 ε 和 (G)α′ 给出 (G)χ′ 的一个下界。
7,设 G 是一个无环边的图,3)( =Δ G 且 G 包含一个生成二部子图 H，使得 ()vVG?∈,
1
() ()
2
HG
dv dv≥,则 4)( ≤′ Gχ 。
8,设 G 是二部图，且 0)( >Gδ,证明：图 G 有一种 )(Gδ 边染色，使得所有的色都在 G
的每个顶点上出现。
9,证明：每个 3 正则 Hamilton 图都有正常 3 边着色。
10,证明：对任何图 G，
3
(G) (G)
2
χ′ ≤Δ 。
11.证明,(1)若 G 是无环简单图，且 () 2 1,() ()Gn GnGυ ε= +>Δ，则 1)()( +Δ=′ GGχ 。
(2) 利用上述结果证明,
(a) 若 G 是一个由顶点数为偶数的无环正则简单图剖分一边后所得之图，则
1)()( +Δ=′ GGχ ；
(b) 若 G 是一个由顶点数为奇数的无环 k－正则简单图去掉少于
2
k
条边后得到的图，则
1)()( +Δ=′ GGχ 。
12,证明：若 G 是非空正则简单图，且 ()Gυ 为奇数，则 1)()( +Δ=′ GGχ 。
13,证明：若 G 是有割点的正则简单图，则 1)()( +Δ=′ GGχ 。
14,设图 G 的边独立数是 (G)α′ 。证明：如果 (G) (G) (G)ε α′>Δ,则 G 是第二类图。利用此结果证明：如果 (G) (G)
2
υ
ε
>Δ?
，则图 G 是第二类图。
15,证明：对不是奇圈的连通图，如果它的所有圈有相同的奇偶性，则 (G) (G)χ′ =Δ 。
27
16,设 G 为 υ阶简单图,证明,若 G 中恰有一个点的度达到 1υ?,则 (G) (G) 1χ υ′ =Δ =? 。
17,证明或否定：如果 G
1
和 G
2
是第一类图，且
12
GHG，则 H 是第一类图。
18,设 G 是简单图,x 与 y 是 G 中两个不相邻的顶点,π 是 G 的一个正常 k 边染色。证明：
若在该染色下 x,y 以及 x 的所有邻点均有颜色未在其上体现,则 G xy+ 也可 k 边正常染色。
19,利用上题的结果证明 Vizing 定理。并证明：若无孤立点的简单图 G 恰有一个度为 (G)Δ
的顶点，或 G 恰有两个度为 (G)Δ 的顶点但这两个顶点相邻，则 G 是第一类图，即
(G) (G)χ′ =Δ 。
20,求下列图的色数。
21,轮图
1,n
W 是由一个点与长为 n 的圈上所有顶点相连形成的图，
1,5
W 如下所示。证明
1,5
()4Wχ = 。
22,证明,
（1） 1)( =Gχ?
ν
KG = ；
（2） 2)( =Gχ?G 是非空二部图；
（3） )()( GG νχ =?
ν
KG? 。
（4）
3)(
12
=
+n
Cχ 。
（5） 3)( ≥Gχ? G 含有奇圈。
23,证明,
（1） G 是临界 1 色图?
1
G K? ；
（2） G 是临界 2 色图?
2
G K? ；
（3） G 是临界 3 色图?G 是奇圈；
（4） 任何 k 色图都包含临界 k 色子图；
（5） 每个色临界图都是连通的简单图。
24,下图是不是临界 3 色图？如果是，给出证明；如果不是，求出它的一个临界 3 色子图。
v
5
v
7
v
4
v
3
v
2
v
1
v
6
28
25,证明：下列 Gr?tzsch 图是临界 4 色图。
Gr?tzsch 图
26,设 H 是图 G 的子图，证明 (G) (H)χ χ≥ 。
27,设
12
,,,
k
GG Gnull 是图 G 的所有块，证明,() max{( )}
i
i
GGχ χ= 。
28,给出一个图 G 使得它有顶点 v 满足 ()()Gv Gχ χ? <,且 ()()Gv Gχχ?< 。
29,证明或否定：任何 k 色图 G 有一个正常 k 染色使得某个色类含 (G)α 个顶点。
30,证明或否定：对任何连通图 G，有
2
(G) 1
ε
χ
υ
≤+,（
2ε
υ
是图 G 的顶点平均度） 。
31,两个图 F 与 H 的并 FH∪ 是以图 F 和 H 的顶点集的并作为顶点集，且以 F 和 H 的边集的并作为边集形成的图。证明或否定：若 GFH= ∪,则 (G) (F) (H)χ χχ≤ + 。
32,设 G 和 H 不相交（即无公共点）,GH+ 表示 G 和 H 的 不交并 （即将 G 和 H 作为分支放在一起组成的图） 。证明 (G H) max{ (G),(H)}χ χχ+= 。
33,图 G 和 H 的 联 GH∨ 表示将 G 的每个顶点与 H 的每个顶点间都连边后形成的图。 证明
(G H) (G) (H)χ χχ∨= + 。
34,设 G 是完全图 K
r
与长为 5 的圈 C
5
的联：
5
G
r
CK= ∨,证明,(G) (G)χ ω> 。并证明 G 是一个色临界图。
35.设 I 是色临界图 G 的任一个点独立集，证明,(G I) (G) 1χ χ? =?。
36,证明：若 G 的任二奇圈都有公共顶点，则 5)( ≤Gχ 。
37,证明：若 G 的任二圈都没有公共顶点，则 () 3Gχ ≤ 。
38,证明：若 G 是简单图，则
2
2
()
2
G
υ
χ
υ ε
≥
。
39,证明：若 G 是二部图，则 (G) (G)χω= 。
40,证明：若 G 中最长奇圈的长度为 m ≥ 3，则 (G) 1mχ ≤ + 。
41,(1) 设简单图 G 的顶点集为
12
{,,,}vv v
υ
null,证明,如果每个
j
v 最多只与
12 1
{,,,}
j
vv v
null
29
中的 k 个顶点相邻（ 2 j υ≤≤）,则有 (G) 1kχ ≤ + ；
(2) 利用 (1)证明：对任何简单图 G 都有 (G) (G) 1χ ≤Δ+；
(3) 利用 (1)证明：对任何简单图 G 都有
H
(G) max (H) 1χ δ≤ +,其中 H 取遍 G 的所有点导出子图；
(4) 利用 (3)证明：若 G 是连通简单图但不是正则图，则 (G) (G)χ ≤ Δ ；
(5) 利用 (4)证明：若 G 是连通的正则简单图且含有 1 顶点割，则 (G) (G)χ ≤Δ ；
(6) 利用 (4)证明,若 G是连通的 k正则简单图 ( 3k ≥ ),且 G有 2顶点割,则 (G) (G)χ ≤Δ ；
(7) 利用上述结论证明 Brooks 定理：设 G 是连通简单图，且既不是奇圈也不是完全图，
则 (G) (G)χ ≤Δ 。
42,求下列两图的色多项式。
43,使用边的删除和收缩方法，并利用树和完全图的色多项式的结果，求 C
4
的色多项式。
44,证明,(,) ( 1) ( 1) ( 1)
nn
n
PC k k k=?+。
45,证明：若
1
HGK=∨，则 (,) (,1)PHk k PGk=。利用这一结果和上题结论证明：
对有 n 根辐条的轮图
1,n
W,
1,
(,) ( 2) ( 1) ( 2)
nn
n
PW k k k k k=?+。
46,利用树和 C
4
的色多项式结果，求下图的色多项式。
47,证明,（ 1）若图 G 含有 r 个孤立顶点，则色多项式 (,) (,)
r
PGk k PG k′=?,其中 G′是
G 去掉 r 个孤立顶点后所得的图； （ 2）若图 G 有重边和环边，用
1
G 表示 G 去掉重边和环边后所得的图，则
1
(,) (,)PGk PG k= 。
48,设 v 是图 G 的一个 1 度顶点，利用上题结论证明,(,) ( 1)(,)PG k k PG v k=。
49,设 G 是连通图，证明：
1
(,) ( 1)PGk kk
υ?
≤?。
50,证明：如果 G 至少含有一条边，则其色多项式的系数之和等于零。
51,证明,Petersen 图不是完美图。
第六章 染色理论
许多实际问题可以归结为求图的匹配或者独立集。 此外,在许多应用中,人们希望知道：
一个给定的图,它的边集至少能划分成多少个边不交的匹配？或它的顶点集至少能划分成多少个点不交的独立集？这便是图的边染色和顶点染色问题。
§ 6.1 边染色
定义 6.1.1 非空无环图 G 的 边正常 k 染色 （ proper edge k- colouring）是 指 k 种颜色 12,knull，，
对 E(G)中元素的一种分配，使得相邻两条边所染颜色不同。换句话说,G 中边正常 k 染色
是映射
},,2,1{)(,kGEc null→,
使得对每个 i ( ki,,2,1 null= ),)(
1
ic
是匹配或者空集。
注,若 令 ),,2,1(},)()({)(
1
kiiecGEeicE
i
null==∈==
，则 G 的一个边正常 k 染色可看成是边集的一种划分 ),,,(
21 k
EEEc null=,其中每个 E
i
是匹配或空集。
例如，下面给出了 5-圈的一种边正常 3 染色和 Petersen 图的一种边正常 4 染色。
定义 6.1.2 若存在 G 的一种边正常 k 染色，则称 G 是 边 k 色可染的 （ edge k-colourable） 。
注,（ 1）每个无环非空图的边必 ε 色可染。
（ 2）若 G 是边 k 色可染的，则对 kl ≥?,G 也是 l 色可染的。
定义 6.1.3 正整数 GkG min{)( =′χ 是边 k 色可染的 }称为 G 的 边色数 (edge chromatic
number)。
注,（ 1）若 kG ＝)(χ′,则 G 中边的任何 k 染色 ),,,(
21 k
EEEc null= 中每个 E
i
都是非空的匹配。
（ 2） G 的边色数 )(Gχ′ 是 G 中边不交匹配的最小数目。
（ 3） )(12)(
22 nn
KnK Δ=?=′χ （因完全图 K
2n
有 2n-1 个边不交的匹配）
（ 4） )()( GG Δ≥′χ 。 （设 )()( Gvd Δ=,则与 v 关联的 )(GΔ 条边至少需 )(GΔ 种色才能正常染色） 。
引理 6.1.1,设 G 是非空无环的连通图，且不是奇圈，则存在 G 的边 2-染色，使得所用的两种色在每个度 2≥ 的顶点处都出现。
证明,（ 1）设 G 是 Euler 图，则 G 中无奇度点。
若 G 本身是一个偶长度圈，则命题显然。若 G 不是一个偶长度圈，则 G 至少有一个顶点 v
0
满足 4)(
0
≥vd (否则,G 中所有顶点都是 2 度的，由于 G 连通，从而 G 是圈，由引理条件,G 不是奇圈，故为偶圈，矛盾 )。
3
3 4
1
1
3
2
2
31
1
2
4
2 2
3
2
1
1
2
2
设
02110
veevev
ε
null 是 G 的一条 Euler 闭迹。 令 ieE
i
{
1
= 为奇数 },ieE
i
{
2
= 为偶数 }。
于是 c = (E
1
,E
2
) 即为所求的边 2-染色。
需要说明的是,Euler 闭迹从度≥ 4 的顶点出发是必需的。例如在下图中，若从 2 度顶点 u 处出发沿 Euler 闭迹交替地对边进行 2 染色，则 u 点可能仅能获得一种色（如图,1,2
表示两种颜色） 。
(2) 设 G 不是 Euler 图。此时给 G 增添一个新顶点 v
0
，将 v
0
与 G 的每个奇度顶点连一条边，得到一个新图 G
*
。显然 G
*
的所有顶点都是偶数度的，因而是 Euler 图。设
0*)(2110
veevev
Gε
null 是 G
*
的一个 Euler 闭迹，令 ieE
i
{
*
1
= 为奇数 },ieE
i
{
*
2
= 为偶数 }，这样可得 G
*
的一个边 2-染色 ),(
*
2
*
1
*
EEc =,（其中
0
v 点的关联边有可能是同一种色） 。按这种办法给 G
*
的边染色后，去掉
0
v 及其关联的边，便得到 G 的一个边 2-染色。对于 G 中偶度点，它关联的边及其颜色与 G
*
中相同；对 G 的任何奇度点 v，在 G 中比在 G
*
中少关联一条边，但只要 1)( >vd
G
,便有 3)( ≥vd
G
,故由染色的方法知，与 v 点关联的边中两种颜色的都有。这说明 G 的边 2-染色 ))(),((
*
2
*
1
GEEGEEc ∩∩= 即为所求的边 2-染色。证毕。
定义 6.1.4 对于 G 的一个边 k-染色 c,c(v)表示顶点 v 处出现的不同颜色的数目。设 c 与 c′
都是 G 的边 k-染色（未必是正常染色） 。若相应的 c(v)与 )(vc′ 满足,
∑∑
∈∈
>′
)()(
)()(
GVvGVv
vcvc,
则称 c′是对 c 的一个 改进 。不能改进的边 k 染色称为 最佳边 k 染色 。
引理 6.1.2 设 ),,,(
21 k
EEEc null= 是 G 的一个最佳边 k 染色,且存在一个顶点 u 及两种颜色
i 和 j,色 i 不在 u 处出现，而色 j 在 u 处出现了至少两次，则 ][
ji
EEG ∪ 中含 u 的连通分支必是奇圈。
证明,设 G
1
是 ][
ji
EEG ∪ 中含 u 的连通分支。若 G
1
不是奇圈，则由引理 6.1.1,G
1
有一个边-2 染色，其两种色在 G
1
中度 2≥ 的每个顶点处都出现。按这种染色办法用色 i 和 j 给
ji
EE ∪ 中的边重新染色后，得到 G 的一个新的边 k-染色 ),,,(
21 k
EEEc ′′′=′ null,其中 i,j
两色都在 u 处出现，故 1)()( +=′ ucuc,而对 u 之外的其它顶点 v，都有 )()( vcvc ≥′ 。于是
∑∑
∈∈
>′
)()(
)()(
GVvGVv
vcvc 。这与 c 是最佳边 k-染色矛盾。证毕。
定理 6.1.1（ K?nig
[1]
,1916）设 G 是二部图，则 () ()GGχ′ =Δ 。
[1] D,K?nig,über Graphen und ihre Anwendung auf Determinantentheorie und mengenlehre,
Math,Ann.,77(1916),453-465,
证明 （反证法）,假设 () ()GGχ′ ≠Δ 。则由定义 6.1.3 的注（ 4）,() ()GGχ′ >Δ 。设
),,,(
21 Δ
= EEEc null 是 G 的一个最佳边 Δ 染色，则 c 必定不是正常染色。故存在顶点 u 满足 )()( uduc <,因而必有某两条在 u 点相邻的边染了同一种色。 而且,因 () ( )du G≤Δ,故
u
1 2
1 2
1
1
2
3
Δ 种色中必有某种色不在 u 上出现。显然 u 满足引理 6.1.2 的条件，因此 G 中有奇圈。这与
G 是二部图矛盾。证毕。
注,也可按推论 3.3.3，二部图的边集可分解为 )(GΔ 个边不交的匹配，故 () ()GGχ′ =Δ 。
定理 6.1.4 (Vizing 定理,1964) 设 G 是无环非空简单图，则
1)()()( +Δ≤′≤Δ GGG χ 。
证明,首先,)()( GG Δ≥′χ (定义 6.1.3 的注（ 4） )。下证 1)()( +Δ≤′ GGχ (用反证法 )。
假如 1)()( +Δ>′ GGχ,令 ),,,(
121 +Δ
= EEEc null 是 G 的最佳 1+Δ 边染色。因
1+Δ>′χ,故 c 必不是正常染色。设 u 是使 )()( uduc < 的顶点。则必存在色 i
0
,i
0
不在 u
处出现（因 1)( ＋Δ<ud ）,同时也存在色 i
1
,i
1
至少在 u 处出现两次。设 uv 和 uv
1
染有颜色 i
1
（如图） 。
因 1)(
1
+Δ<vd,故必有某种色
2
i 不在 v
1
处出现。这样
2
i 必然在 u 处出现（否则，可用
2
i 给 uv
1
重新染色，得到一个改进的 1＋Δ 边染色，与 c 是最佳染色矛盾） 。因此存在一条边 uv
2
染有色
2
i 。
又因 1)(
2
+Δ<vd,必有某种色
3
i 不在 v
2
处出现。
3
i 必然在 u 处出现 （理由同上） 。
因此存在一边 uv
3
染有色
3
i 。
继续这个过程，可找出一个顶点序列 null,,
21
vv,以及一个颜色序列 null,,
21
ii,使得边 uv
j
染有颜色 i
j
，且色 i
j+1
不在点 v
j
处出现,（ null,2,1=j ） 。而且，因 )()( uduc < 且 )(ud 是有限数，故存在一个最小整数 m，使得对某个 k < m，有 i
m+1
= i
k
。
现在，对 11?≤≤ kj,用颜色 i
j+1
给边 uv
j
重新染色。这样产生一个新的 ( 1＋Δ )边染色
),,,(
121 +Δ
′′′=′ EEEC null 。显然对所有 Vv∈,)()( vcvc ≥′ 。因此 c′也是 G 的一个最佳
)1( +Δ 边染色。由引理 6.1.2,][
0 k
ii
EEG ′′ ∪ 中含有 u 的那个分支
1
H 是个奇圈。
…
u
v
v
3
v
2
v
1
v
k
v
k-1
v
m
i
1
i
1
i
2
i
m
i
k-1
i
k
i
3
…
…
…
u
v
v
3
v
2
v
1
v
k
v
k-1
v
m
i
1
i
2
i
3
i
m
i
k-
i
k
i
4
…
…
i
0
i
0
i
k
i
k
H
1
4
而对 1?≤≤ mjk,用颜色 i
j+1
给 uv
j
重新染色，而用颜色 i
k
给 uv
m
重新染色，得到一个 ( 1＋Δ )边染色 ),,,(
121 +Δ
′′′′′′=′′ EEEc null 。同理有 )()( vcvc ≥′′ 对所有 Vv∈ 成立。故由引理
6.1.2,][
0 k
ii
EEG ′′′′ ∪ 中含有 u 的分支
2
H 是个奇圈。
但是，因 v
k
在
1
H 中的度为 2（恰与一条 i
0
色边和一条 i
k
色边相关联）,故它在
2
H 中的度为 1（仅与一条 i
0
色边相关联） 。这与
2
H 是奇圈矛盾。 （注意 v
k
必在分支
2
H 中，因它与
v
k
－
1
有 i
0
,i
k
交错路（
1
H 的一段）相连） 。由此可知反证法假设不能成立。证毕。
对于有重边的图 G，设 )(Gμ 表示 G 中边的最大重数,Vizing 实际上证明了一个更一般的结论,)()()()( GGGG μχ +Δ≤′≤Δ 。
Vizing 定理提出了一个分类问题：使 )()( GG Δ=′χ 的简单图称为第一类图，使
1)()( +Δ=′ GGχ 的简单图 G 称为第二类图。确定一个图属于第一类还是第二类是很困难的，目前仅对少量的图类判明了它们所属的类。路、树、二部图、偶数阶完全图、轮图都是第一类图（轮图
1,n
W 是由一个点与长为 n 的圈上所有顶点相连形成的图）,奇圈、奇数阶完全图都是第二类图 (见有关定理和习题 )。一般情况下判别一个图属于第几类图，尚没有好的充分必要判别条件，一些充分性判别条件见习题。
第二类图相对较稀少。在 6υ ≤ 的 143 个连通简单图中仅有 8 个属于第二类；而 Erd?s
和 Wilson(1977)已证明,1
|)()(|
|)(|
lim
21
1
=
∞→
νν
ν
cc
c
v
∪
，其中 ()
i
c υ 表示 υ阶第 i 类图的集合。这表明当顶点数充分大时，几乎所有非空简单图都是第一类图。
已经知道存在最大度为 2,3,4,5 的第二类平面图，但 Vizing (1965)已证明：不存在最大度 8≥ 的第二类平面图。目前尚不知道是否存在最大度为 6 或 7 的第二类平面图。
由 Vizing 定理，每个无环非空简单图 G 都是可（ 1+Δ ）边可染色的。实际上，可以根据引理 6.1.1 和引理 6.1.2 给出求图 G 的正常（ 1+Δ ）边染色的多项式时间算法。但是，求一般图 G 的边色数 )(Gχ′ 及其相应的正常边染色尚无多项式时间算法。事实上，已经证明这是一个 NPC 问题
[2]
。求二部图的边色数的一个多项式时间算法将在§ 6.4 中介绍。有关边染色的更多内容可参看 [3]。
[2] I,Holyer,The NP-completeness of edge-coloring,SIAM J,Computing,10(1981),718-720,
[3] S,Fiorini,and R.J,Wilson,Edge-colorings of graphs,Selected Topics in Graph Theory (eds,L,
W,Beineke,and R.J,Wilson),Academic Press,London,(1978) 103-126,
…
u
v
v
3
v
2
v
1
v
k
v
k-1
v
m
i
1
i
2
i
3
i
m
i
k-
i
k
＋
1
i
4
…
…
i
0
i
0
i
k
i
k
H
2
i
k
5
§ 6.2 点染色
一、点染色的基本概念
定义 6.2.1 设 G 是一个无环边的图。 G 的顶点 正常 k 染色 (proper vertex k-colouring)π 是指 k
种颜色 12,knull，，对于 G 的各顶点的一种分配，使得任二相邻的顶点被染上不同的颜色。换句话说,G 的顶点正常 k 染色 π 是一个映射
},,2,1{)(,kGV null→π,
使得 )(
1
i
π 是独立集或空集 ),,2,1( ki null=,
注,设 π 是 G 的一个顶点正常 k 染色。令
})(|)({)(V
1
ixGVxi
i
=∈==
ππ,（ ki,,2,1 null= ） 。
则 π 实际上是对顶点集 )(GV 的一种划分,),,,(
21 k
VVV null=π,其中 φ=
ji
VV ∩,
)(
1
GVV
k
i
i
=
=
∪
，且每个
i
V 是独立集或空集 ),,2,1( ki null=,
例如，下图给出了 Petersen 图的一种定点正常 3 染色。
定义 6.2.2 若存在 G 的一种顶点正常 k 染色,则称图 G 是 点 k 色可染的 (vertex k-colourable),
有时简称为 k 色可染的 或 可 k 染色的 。
注,⑴ 每个图 G 一定是 ()Gυ 色可染的。
⑵ 若图 G 是 k 色可染的，则对任何正整数 km ≥,G 也 m 色可染。
定义 6.2.3 设 G 是无环边的图，令
GkG |min{)( =χ 是 k 色可染的 },
称 )(Gχ 为 G 的 点色数,有时简称为 色数 (chromatic number)。若 kG =)(χ,则称 G 为 k 色图 (k-chromatic graph)。
注,（ 1） 若 kG =)(χ （即 G 是 k 色图）,则 G 中任何点 k 染色 ),,,(
21 k
VVV null=π 中每个
i
V 都是非空的独立集。换言之,G 的色数是 G 中点不交的独立集的最小数目。
（ 2）由色数的定义容易证明如下结论,
z 1)( =Gχ? GK
υ
= ；
z 2)( =Gχ?G 是非空二部图；
z 3)(
12
=
+n
Cχ 。
z 3)( ≥Gχ? G含有奇圈。
z () ()GGχ υ=? GK
υ
。
1
1
3
3
2
2
3 1
1
2
6
点染色理论的基本问题,给定图 G，确定 )(Gχ 的值。
目前,人们仅对某些特殊图类,确定出了计算 )(Gχ 的公式。 对一般图 G,得出了 )(Gχ
的各种上下界。为了介绍有关结果，需要引入色临界图的概念。
二、色临界图
定义 6.2.4 设 )1(,)( ≥= kkGχ 。若对 G 的任何真子图 H，均有 kH <)(χ,则称 G 是 临界
k 色图 （ critical k-chromatic graph）,
注,临界 k 色图实际上就是 k 色极小子图，也就是说，它本身是 k 色的，但任意删去一个顶点或一条边后色数就会减少。按色临界图的概念容易知道下列结论成立
z 3)( ≥Gχ? G含有奇圈。
z G 是临界 1 色图?
1
G K? ；
z G 是临界 2 色图?
2
G K? ；
z G 是临界 3 色图?G 是奇圈；
此外，容易证明,（1）任何 k 色图都包含临界 k 色子图； （2）每个色临界图都是连通的简单图。 （留作习题） 。
定理 6.2.1 色临界图的顶点割集不是团。
证明（反证法）,假设图 G 是一个临界 k 色图，但有一个点割集 S 是团。记 SG \ 的连通分支为
n
GGG,,,
21
null 。将 ][SG 按 G 中的连接方式分别与
n
GGG,,,
21
null 相连，得到子图
n
GGG ′′′,,,
21
null 。
示例:图 G 及点割集 S={u,v}
321
,,GGG ′′′
因 G 是 k 色临界的,故每个
i
G′是 k－ 1 色可染的。 由于 S 是团,所以 S 中各个顶点在
i
G′
的任何 k－ 1 染色中必染到相异的色。我们总可以调整各
i
G′中颜色的编号，使得 S 中每一个顶点在各
i
G′中染相同的色。这些
i
G′的染色合在一起便形成 G 的一个 k－ 1 染色。这与 G 是临界 k 色图矛盾。证毕。
推论 6.2.1 每个色临界图都是块（即不含割点，亦即 2 连通） 。
证明：假如某临界图不是块，则它有割点。这个割点构成一个团，与定理 6.2.1 矛盾。证毕。
下一个推论是显然的。
推论 6.2.2 若临界 k 色图 G 有 2 顶点割集 },{ vu,则 u 与 v 不相邻。
u
v
u
v
u
v
u
v
7
定理 6.2.2 (Dirac,1952) 设 G 是临界 k 色图（ k≥2）,则边连通度 1)(?≥′ kGκ 。
证明：若 k = 2，则
2
KG?,故 1)( =′ Gκ 。
下设 3≥k,用反证法。
假如 1)(?<′ kGκ,则存在 )(GVS? 使得 1)(|),(|?<′= kGSS κ 。因 G 是临界 k
色图，故 ][
1
SGG = 与 ][
2
SGG = 中的顶点都 1?k 色可染。设 ),,,(
1211?
=
k
UUU nullπ 和
),,,(
1212?
=
k
WWW nullπ 分别是
1
G 和
2
G 中点的 1?k 染色。构造二部图
),( YXH =,},,{
1,21?
=
k
xxxX null,},,{
1,21?
=
k
yyyY null,
其中?∈ )(HEyx
jii
U 的点与
j
W 的点在 G 中无连边。
因 1)(|),(|?<′= kGSS κ,故 )2)(1()1()1()(
2
=> kkkkHε 。（注意 X 与
Y 间共可连出
2
)1(?k 条可能的边；其次，因在 G 中 S 与 S 间连边数 1?< k,故 X 与 Y 间在 H 中不能连的边数 1?< k ） 。
我们来证明 H 必有完美匹配。
事实上,H 的点覆盖数 1)(?≥ kHβ （否则，若 2)(?≤ kHβ,则因 1)(?≤Δ kH,H
的每个顶点至多能覆盖 1?k 条边。这样 )1)(2()1()()(≤≤ kkkHH βε,与
)2)(1()(> kkHε 矛盾） 。由 K?nig 定理（第五章定理 5.2.2）,1)()(?≥=′ kHH βα 。
这表明 H 有完美匹配（因对于 H,1?== kYX ） 。
设 H 的一个完美匹配为 M
*
,}1,,2,1{
*
== kiyxM
i
ji
null,相应地
i
jii
WUV ∪=,
则 V
i
是 G 的独立集（ 1,,2,1?= ki null ）,因此 ),,,(
121?
=
k
VVV nullπ 是 G 的一个点 k-1 染色。
但这与 kG =)(χ 矛盾，故 1)(?≥′ kGκ 。证毕。
推论 6.2.3 设 G 是临界 k-色图，则 1)(?≥ kGδ 。
证明：由定理 )()()( GGG κκδ ≥′≥ 及定理 6.2.2，有 1)()(?≥′≥ kGG κδ 。证毕。
推论 6.2.4 任何 k 色图至少有 k 个顶点的度 1?≥ k 。
证明：设 G 是 k 色图,H 是其一个临界 k 色子图，由推论 6.2.3,H 的每个顶点在 H 中的度
1?≥ k,故在 G 中的度也 1?≥ k 。由于 H 是 k 色临界的，因此它至少有 k 个顶点。证毕。
三、色数的上下界
U
1
U
2
U
k -1
null
S
W
1
W
2
W
k-1
null
S
x
1
x
2
x
k-1
y
2
y
k-1
y
1
null
null
H
8
定理 6.2.3 对任何简单图 G,1)()( +Δ≤ GGχ 。
证明：设 kG =)(χ,且 H 是 G 的临界 k 色子图，由推论 6.2.3,1)(?≥ kHδ 。故
1)(1)()()(?=?≥≥Δ≥Δ GkHHG χδ 。证毕。
定理 6.2.3 给出的上界是可以达到的，例如奇圈和完全图的色数恰好等于它们的最大度加 1。下面来证明，达到这个上界的连通简单图只有这两类图。
定理 6.2.4 (Brooks,1941) 设 G 是连通的简单图，且 G 既不是奇圈又不是完全图，则
)()( GG Δ≤χ 。
证明：设 G 是满足定理条件的 k 色图。
Case1,G 本身是临界 k 色的。
由推论 6.2.1,G 是一个块。又由于临界 1 色图和临界 2 色图是完全图，而临界 3 色图是奇圈，故 4≥k 。由推论 6.2.3,(G) 3δ ≥ 。
如果 G 是 3 连通的,则因 G 不是完全图,故必存在顶点 )(,,GVzyx ∈,使得 )(GExy?,
而 )(,GEyzxz ∈,并且 G{,}x y? 连通。如果 G 的连通度为 2，则 G 中存在一点 z，使得
G{}z? 有割点且连通，此时 G{}z? 至少有两个连通块只含 1 个割点（见第二章习题）,设
B
1
,B
2
为这样两个块。 因 G 本身 2 连通且无割点,故 B
1
,B
2
均有点在 G 中与 z 相邻。 设
1
Bx∈
和
2
By∈ 是两个与 z 相邻的点。由于 x
1
和 x
2
在不同的块中，因此它们在 G{}z? 中不相邻，
因而在 G 中也不相邻，且因 () ( ) 3
G
dz Gδ≥≥,G{,}x y? 连通。
总之，必存在顶点 )(,,GVzyx ∈,使得 )(GExy?,)(,GEyzxz ∈ 且 G{,}x y? 连通。
给 G 的顶点重新编号：首先 yxxx ==
21
,,然后对 },{\ yxGG =′ 中的顶点，按 G′中到 z
的距离由远及近的次序依次用
34
,,,x xx
υ
null 编号，即,),(),(
1
zxdzxd
iGiG +′′
≥,
( 3,4,,i υ= null ),（注意 G′仍连通） 。
因此 x z
υ
=,且对每个 1,2,,1i υ=?null,必存在 ij > 使得 ()
ij
x xEG∈ 。由此可知，
对每个 1,2,,1i υ=?null,
i
x 与 },,,{
121?i
xxx null 中最多 1)(?Δ G 个顶点相邻（因与
i
x 相邻的至少有一个顶点的下标 i> ）,且因 3)()( ≥≥ Gzd δ,故
1
()x xEG
υυ?
∈ 。
这样一来,可用 )(GΔ 种颜色给顶点进行染色,将 x
1
和 x
2
染色 1,然后按颜色 Δ，，,null21
的顺序依次给
34
,,,x xx
υ
null 进行染色，使相邻两点染不同的色。染法为,
设
11
,,
i
xx null 已染好，考虑 x
i
,( 31i υ≤ ≤?)。由于 x
i
仅与
11
,,
i
xx null 中最多 1)(?Δ G
个顶点相邻，所以 Δ，，,null21 种颜色中至少有一种颜色 α 在 },,,{)(
121?ii
xxxxN null∩ 中未
(x
1
)
x
7
x
6
x
5
x
4
x
3
(x
2
)
z
x
9
x
y
x
8x
10
9
曾用过，因此可给点
i
x 染以颜色 α 。因 x
υ
(=z)既与 x
1
又与 x
2
相邻，且 x
1
和 x
2
染的色相同，
所以 Δ 种色中同样也有一种色 β 在 (Nx
υ
)中未曾用过,（因 ()dx
υ
≤ Δ,而 x
υ
的邻点中已有两点染同一种色，故 Δ 种色不会全在 ()Nx
υ
中出现） 。因此可给 x
υ
染以色 β 。
如此便得图 G 的一个正常 Δ -染色，即有,)()( GG Δ≤χ 。
Case2,G 不是 k 色临界的。此时取 G 的一个临界 k 色子图 H。
(1) 若 H 是完全图，则 H＝
k
K,从而
)(1)(1)1()()( GHkkHG Δ≤+Δ=+?=== χχ （ G 中有不属于 H 的边和点） ；
(2) 若 H 是一个奇圈，则 )(3)()( GHG Δ≤== χχ （ G 中至少有一条不属于 H 的边） 。
(3) 若 H 既不是完全图，也不是奇圈，则由 Case1 的证明可知 )()()( GHH Δ≤Δ≤χ,
从而 )()()( GHkG Δ≤== χχ 。
证毕。
例 6.2.1 求 Peterson 图的色数。
解：因 Peterson 图 G 含有奇圈，故不是二部图，因而 3)( ≥Gχ ；
另一方面,G既不是奇圈又不是完全图，且 3)( =Δ G,
故 3)()( =Δ≤ GGχ 。因此,3)( =Gχ 。
虽然奇圈和完全图可以达到定理 6.2.3 提供的色数上界 ()1GΔ +,但某些图类的色数与这个上界相差很远，比如星图
1,
K
n
的色数为 2，
1,
(K ) 1
n
nΔ +=+1。下面给出的几个上界在某种程度上是对定理 6.2.3 的改进。
定理 6.2.5 设连通简单图 G 的度序列为
12
dd d
υ
≥≥≥null,则
(G) 1 max min{,1}
i
i
diχ ≤ +?
证明：将 G 的所有顶点按度的递减（不增）顺序排序，设为
12
,,,vv v
υ
null 。从 v
1
开始依次给顶点染色。在第 i 次染色时，用 v
i
的邻点尚未使用的颜色中色号最小的颜色给 v
i
染色（事先对使用的颜色编号）,(1,2,,)i υ= null 。由于对 v
i
染色时，下标比 i 大的顶点尚未染色，而下标小于 i 的顶点中与 v
i
相邻的顶点不超过 min{,1}
i
di? 个，因此以使用的颜色数也不会超过 min{,1}
i
di?,从而按染色规则，对 v
i
染色使用的颜色编号不会超过 min{,1}
i
di? +1。
时。这个结论对所有 1,2,,i υ= null 都成立。因此将 G 的所有顶点全部染色使用的颜色不会超过 max min{,1} 1
i
i
di? + 种。证毕。
定理 6.2.5 对任何图 G，
HG
(G) 1 max (H)χ δ
≤+ 。
证明：对于空图，结论显然成立。因此可设 (G) 2kχ = ≥ 。
取 G 的一个临界 k 色子图 H
0
，则
0
HG
(H ) max (H)δ δ
≤ 。由推论 6.1.3,
1
1
3
3
2
2
3 1
1
2
10
00
HG
(G) (H ) 1 (H ) 1 max (H)kχ χδ δ
= =≤+ ≤+ 。
证毕。
定理 6.2.6 用 (G)l 表示图 G 中最长路的长度，则 (G) 1 (G)lχ ≤ + 。
证明：结论对于空图显然成立。因此可设 (G) 2kχ = ≥ 。
取 G 的一个临界 k 色子图 H，由推论 6.2.3，则 (H) 1kδ ≥?。用最长路方法不难证明，
H 中有长为 (H)δ 的路。因此 (G)l (H) 1kδ≥≥?。从而 (G) 1 (G)klχ = ≤+ 。证毕。
关于色数的下界有如下定理。
定理 6.2.7 对任何图 G，
2
2
(G) 1
ε
χ
υ
≥+
证明：设 G 的色数是 k，则有 )(GV 的一种划分,),,,(
21 k
VVV null=π,其中 φ=
ji
VV ∩,
)(
1
GVV
k
i
i
=
=
∪
，且每个
i
V 是非空的独立集 ),,2,1( ki null= 。按分组
12
,,,
k
VV Vnull 的次序将 G
的所有顶点依次编号后，其邻接矩阵可写为如下分块形式
11 12 1
21 22 2
12
A(G)
k
k
kk k
AA A
AA A
AA A
=
null
null
nullnullnullnull
null
其中主对角线上每个
ii
A 都是零矩阵。
设 ||
ii
Vp=,则矩阵 A(G)中至少有
2
1
k
i
i
p
=
∑
个零元素。另一方面,A(G)共有
2
υ 个元素但
G 只有 ε 条边。由邻接矩阵的对称性,ε 条边在 A(G) 中形成 2ε 各非零元素，故 A(G)中零元素的个数应为
2
2υ ε? 个。由以上两方面，有
2
2υ ε? ≥
2
1
k
i
i
p
=
∑
。利用柯西不等式
22 2
11 1
()()( )
kk k
ii i
ii i
ab ab
== =
≥
∑∑ ∑
，有 k?
2
1
k
i
i
p
=
∑
≥
22
1
()
k
i
i
p υ
=
=
∑
。从而
2
2υ ε? ≥
2
k
υ
。由此解得
2
2
1k
ε
υ
≥+，即
2
2
(G) 1
ε
χ
υ
≥+
。证毕。
图的色数与独立集和团有关。利用一个图的独立数和团数，可以获得其色数的上下界。
定理 6.2.8 对任何图 G，有（ 1） (G) (G) 1χ αυ+ ≤+,（ 2） (G) (G)χ αυ? ≥ 。 （ (G)α 是
G 的点独立数）
证明,（ 1）设 I 是 G 的一个最大点独立集，则 | I | = (G)α 。给 I 中的点染上一种颜色,G
中其余 (G)υ α? 个顶点每点染一种不同的颜色，这样得到 G 的一个 (G) 1υ α? + 种颜色的正常染色，因此 (G) (G) 1χ υα≤? +。
（ 2） 设 (G) kχ = 。按定义,V(G)可划分为 k 个非空独立集
12
,,,
k
VV Vnull,则
(G) | |
i
Vα ≥,1,2,,ik= null 。从而
1
() | |
k
i
i
kG Vα υ
=
≥=
∑
，即 (G) (G)χ αυ? ≥ 。
11
定理 6.2.9 对任何图 G，有 (G) (G)χ ω≥,(G)ω 是 G 的团数。
证明,设 W 是 G 的一个最大团，因 W 中所有点都在 G 中彼此相邻，因此对 G 染色时 W 的每个点需要一种不同的颜色，故 (G) (G)χ ω≥ 。证毕。
Reed 在 1998 年提出一个猜想
[4]
：图的色数的上界 (G)+1Δ 和下界 (G)ω 的平均值也是色数的一个上界，即
(G) 1 (G)
(G)
2
ω
χ
Δ++
≤
。这个猜想尚未得到证实。
Borodin 和 Kostochka 曾猜想
[5]
，当 (G) 9Δ ≥ 时，如果 (G) (G)ω <Δ,则
(G) (G)χ <Δ 。 1999 年 Reed 证明了在
14
(G) 10Δ≥ 时，上述结论是正确的
[6]
。
[4] B,Reed,,,andω χΔ,J,Graph Theory,27(1998),177-212,
[5] O.V,Borodin,and A.V,Kostochka,On an upper bound of the graph’s chromatic number
depending on the graph’s degree and density,J,Comb,Theory (B),23(1977)247-250,
[6] B.Reed,A strengthening of Brooks’ theorem,J,Comb,Theory(B),76(1999),136-149,
按照定理 6.2.9，一个图有大的团则必有大的色数。直觉上看，反过来也应该成立，即
G 的色数较大则它应该也含有大的团，或者说团数 (G)ω 较小时色数 (G)χ 也会较小。已被部分证实的上述 Borodin-Kostochka 猜想似乎也支持这一说法。但令人惊奇的是，事实并非如此。下一个定理表明，存在 (G)ω =2 但 (G)χ 可以任意大的图。
定理 6.2.10 对任意的正整数 k，存在不含三角形的 k 色图。
证明：对 k=1,2，定理的结论显然成立。下设 3k ≥ 。一个不含三角形的 3 色图是长为 5 的圈 C
5
。下面我们从 C
5
出发递推地由某个不含三角形的 k 色图 G
k
构造不含三角形的 k +1 色图 G
k+1
。构造方法如下：设 G
k
的顶点集为 {
12
,,,
n
uu unull }，给 G
k
添加 n+1 个新顶点
12
,,,,
n
vv vvnull,每个 v
i
与 u
i
在 G
k
中的所有邻点连边，同时也与 v 连边,1,2,,in= null 。例如由 C
5
按上述方法构造出的图如下，该图称为 Gr?tzsch 图。容易检验它是一个无三角形的
4 色图（习题） 。下面证明按这种方法构造出的 G
k+1
都是无三角形的 k+1 色图。
令 V
*
={
12
,,,
n
vv vnull }。假如 G
k+1
中有三角形 C
3
，则 C
3
中必含有 V
*
的点。另一方面，
因 V
*
是独立集，故 C
3
中至多含 V
*
中的一个点，由于 v 仅与 V
*
中点有连边，因此不可能出现在 C
3
上。无妨设 C
3
的顶点是,,
ijt
uu v。按 G
k+1
的构造方法，与除 v
t
相邻的旧顶点一定与
u
t
相邻，这表明,,
ijt
uu u是 G
k
中的一个三角形。这与 G
k
中不含三角形矛盾，因此 G
k+1
中不可能出现三角形。
C
5
u
1
u
3
u
2
u
3
u
5
v
1
v
2
v
3v4
v
5
v
u
1
u
3
u
2
u
3
u
5
Gr?tzsch 图
12
设 (G )
k
kχ =,我们来证明
1
(G ) 1
k
kχ
+
= + 。
首先在 G
k
的正常 k 染色基础上，可得到 G
k+1
的正常 k+1 染色。事实上，由于在 G
k+1
中每个 v
i
与相应的 u
i
不相邻，因此只要给 v
i
染 u
i
原有的颜色（ 1,2,,in= null ）,而给 v 染第
k+1 种颜色，即可将 G
k
中的正常 k 染色扩充为 G
k+1
中的正常 k+1 染色。由此可知
1
(G ) 1
k
kχ
+
≤+。
下面来证明
1
(G ) 1
k
kχ
+
≥+，用反证法。假定
1
(G )
k
kχ
+
≤,则因 G
k+1
的子图 G
k+1
的色数为 k，因此必有
1
(G )
k
kχ
+
= 。设 π 是 G
k+1
的一个正常 k 染色，通过对颜色重新命名，
总可假定 v 染第 k 种色。 由于 v 与所有 v
i
相邻,因此
12
,,,
n
vv vnull 的颜色全在 {1,2,,1k?null }
中。设在当前染色下，顶点
12
,,,
n
uu unull 中染第 k 种颜色的顶点的集合为 V
k
。对
ik
uV?∈，
将其染色改为 ()
i
vπ 。我们来证明经过这种改动后，得到 G
k
的正常 k?1 染色。
事实上,(1) 由于在原来的染色下
k
V 中的顶点染相同的色，因此
k
V 中的顶点互不相邻。
(2) V(G )
kk
V? 中的所有顶点染色未作改变，因此其中相邻的顶点保持不同的色。
(3) 对
ik
uV?∈和 ()
jkk
uVG V?∈?，如果它们相邻，则由 G
k+1
的构造知,u
i
的相应顶点 v
i
也与 u
j
相邻，因此在原有染色中 u
j
与 v
i
染有不同的色，而染色改动后 u
i
的颜色正是 v
i
的颜色,u
j
的颜色未变，可见颜色改动后 u
i
与 u
j
异色。由以上三种情况可知改动后的染色的确是 G
k
的正常 k?1 染色。但这与 G
k
是 k 色图矛盾。
至此，我们已证明了 G
k+1
是无三角形的 k+1 色图。证毕。
该定理中由某个不含三角形的 k 色图 G
k
构造不含三角形的 k +1 色图 G
k+1
的构造方法称为 Mycielski 构造 。
13
§ 6.3 色多项式
本节要考虑的问题是：对于给定的（标定）图 G，用 k 种颜色（ k≥ 1）对 G 进行正常顶点染色，共有多少种不同的染色方式？这里两种染色方式不同，是指至少有一个顶点在这两种染色方式下染有不同的色。
例如，用三种方式给 K
3
染色，不同的染色方式有 6 种。
我们用 P(G,k)表示使用 k 种色对图 G 的顶点正常染色的不同方式数。 P(G,k)是 k 的一个函数，定义域为自然数集。以下将会看到，对一个给定的图 G,P(G,k)是一个关于 k 的多项式。这个多项式称为图 G 的 色多项式（ chromatic polynomial） 。
定理 6.3.1 (1) P(G,k) > 0 的充分必要条件是 ()Gkχ ≤ ；
(2) ()G0ε = （即 G 是空图）时,(,)PGk k
υ
= ;
(3) 若
υ
=GK（即 G 是 υ阶完全图）,则 (,) ( 1) ( 1)PGk kk k υ=+null 。
证明,（ 1） P(G,k)>0 当且仅当 G 至少有一种 k 正常染色，即 ()Gkχ ≤ 。
（ 2） G 是空图则 G 的每个顶点都可以用 k 种颜色中的任一种来染色，故 (,)PGk k
υ
= 。
（ 3） G 是完全图
υ
K,则 G 中第一个顶点有 k 种色可选，第二个顶点有 k?1 种色可选，…，
第 ν 个顶点有 1k υ?+种色可选。故 (,) ( 1) ( 1)PGk kk k υ=+null 。证毕。
设 e 是图 G 的一条边，我们用 G? e 表示边的收缩，即从 G 中删去 e 并将 e 的两个端点粘和在一起后所得的图。
定理 6.3.2 设 G 是简单图，对任意 ()eEG∈,有 (,) (,) (,)PGk PG ek PG ek=。
证明：设 e= uv，考虑用 k 种颜色对 G?e 染色的方式。
（ 1）对 G?e 染色且使 u 与 v 染同色的方式数恰为 P(G? e,k)；
（ 2）对 G?e 染色且使 u 与 v 染异色的方式数恰为 P(G,k)。
因此,(,) (,) (,)PGk PG ek PG ek=。证毕。
利用定理 6.3.2 给出的公式，可以通过减边或增边及边的收缩运算求得一些小阶图的色多项式。
例 6.3.1 求
1,3
K 和
4
C 的色多项式。
=
432
33kkkk?+?,
=
)?(= (
) =
3 ( )? ) + 3 (
1
3 2
v
1
v
2
v
3
3
2 1
v
1
v
2
v
3
2
13
v
1
v
2
v
3
1
23
v
1
v
2
v
3
3
12
v
1
v
2
v
3
2
3 1
v
1
v
2
v
3
14
= (1)(2)(3)2(1)(2)(1)kk k k kk k kk++?
2
(1)( 33)kk k k=+,
定理 6.3.3 设 ()
r
hG表示将 G 的顶点集划分为 r 个非空独立集的划分个数，则
1
(,) [ ( ) ( 1)( 2) ( 1)]
r
r
PGk h Gkk k k r
υ
=
=+
∑
null 。
证明：对每个正整数 r,(1 rk≤≤)，如果 G 不存在正常 r 点染色，则 ()
r
hG=0；如果 G 存在正常 r 点染色（恰使用 r 种颜色）,则 G 的顶点集可划分为 r 个非空独立集
12
,,,
r
VV Vnull 。
现用 k 种颜色给这些独立集染色 ()kr≥,使得每个独立集的顶点染一种色，不同独立集的顶点染不同的色，共有 (1)(2)( 1)kk k k r+null 中染法。每一种染法都给出 G 的一个正常 k 点染色。由于将 G 的顶点集划分为 r 个非空独立集的划分有 ()
r
hG种方式，因此对应于
r个独立集划分的各种可能方式共能得到图 G的 ()
r
hG? (1)(2)( 1)kk k k r+null 种正常
k 点染色。 当 r 从 1 取至 k 时,得到
1
[()( 1)( 2) ( 1)]
k
r
r
hGkk k k r
=
+
∑
null 种正常 k 点染色，
这些点染色显然是不同的正常 k 点染色。由于 G 的每种正常 k 点染色都可看作将 G 的顶点集划分为 k 个独立集（可以有空集）,因此都在上述计数之内。这说明 G 的正常 k 点染色的方式数恰为
1
[()( 1)( 2) ( 1)]
k
r
r
hGkk k k r
=
+
∑
null,即
1
(,) [ ( ) ( 1)( 2) ( 1)]
k
r
r
PGk h Gkk k k r
=
=+
∑
null 。
当 k υ< 且 rk> 时,(1)(2)( 1)kk k k r+null = 0；当 k υ> 且 r υ> 时,()
r
hG= 0。
因此上式与
1
(,) [ ( ) ( 1)( 2) ( 1)]
r
r
PGk h Gkk k k r
υ
=
=+
∑
null 等价。证毕。
我们利用定理 6.3.3 来求 C
4
的色多项式。将 C
4
划分为两个点独立集只有一种方式，即相间隔的两点作为一个独立集，因此
24
()1hC = ；将 C
4
划分为三个点独立集有两种方式：
相间隔的两点作为一个独立集，另两点各自作为独立集，因此
34
()2hC = 。此外，显然
14
()0hC =,
44
()1hC = 。按定理 6.3.3,
2
4
(,)1( 1)2( 1)( 2)1( 1)( 2)( 3) ( 1)( 3 3)PC k kk kk k kk k k kk k k= + + = +,
这与前面计算的结果一致。
定理 6.3.4 对任何简单无环图 G,P(G,k)是 k 的整系数 υ次多项式，且
（ 1）首项为 k
υ； （ 2）第二项为
1
k
υ
ε
； （ 3）常数项为零； （ 4）系数正负交替出现。
证明,对 ε 作归纳。无妨设 G 是简单图。
0ε = 时,(,)PGk k
υ
=,结论成立。
假设 1mε ≤?时结论成立。考虑 mε = 的情形。由归纳假设,
= +) + (++ + + 2) == (
15
2
1
1
(,) (1) (1)
ii
i
i
PG ek k k ak
υ
υυ υ
ε
=
= +?
∑
,
1
(,) (1)
ii
i
i
PG ek k k bk
υ
υυ υ
ε
=
′?=? +?
∑
3
12 1
,
其中 ε′是 G?e 的边数,a
i
,b
i
是非负整数。由定理 6.3.2,
(,) (,) (,)PGk PG ek PG ek=
2
1
1
(1) (1)
ii
i
i
kk ak
υ
υυ υ
ε
=
= +?
∑
1
[()]
ii
i
i
kk bk
υ
υυ υ
ε
=
′ +?
∑
3
12 1
12
2
1
() (1)()
ii
ii
i
kk ak abk
υ
υυ υ υ
υ
εε
=
′=? ++ +? +
∑
3
。
证毕。
下一个定理是显然的。
定理 6.3.5 （ 1）若图 G 有 w 个连通分支 G
1
,G
2
，…,G
w
，则
1
(,) (,)
w
i
i
PGk PG k
=
=
∏
。
（ 2） P(G,k)中系数非零的项的最低次幂为 k
w
，其中 w 是 G 的连通分支数。
定理 6.3.6 G 是树的充分必要条件是 (,) ( 1)PGk kk
υ?
=?
1
。
证明,充分性。 设 (,) ( 1)PGk kk
υ?
=?
1
,则色多项式的最低次幂是 k 的 1 次项。 由定理 6.3.5
知,w=1，即 G 是连通图；又因 (1)kk
υ?
1
的 υ?1次项的系数是 ()υ1,故 ε υ=?1。
因此 G 是树。
必要性。设 G 是树。下面对 G 的顶点数 υ用归纳法来证明 (,) ( 1)PGk kk
υ?
=?
1
。
当 υ = 1时，显然 P(G,k) = k，结论成立。
假设对 1nυ ≤?的所有树，结论成立。
对 nυ = 的任何树 G，取 G 的一个叶顶点 v
0
，令 G′= G? v
0
，则由归纳假设,
()-1 ()2
(,) ( 1) ( 1)
GG
PG k kk kk
υυ′?
′ =? =? 。
注意对 G′的每一个点正常 k 染色,v
0
有 k?1 种染色法使 G 正常染色，故
()
(,) (,)( 1) ( 1)
G
PGk PG k k kk
υ?
′=?=?
1
。
定理 6.3.7 设 G 是圈，则 (,) ( 1) ( 1) ( 1)PGk k k
υυ
=?+。
证明,对 G 的顶点数 υ作归纳。
υ = 3时,G 是完全图 K
3
，故 P(G,k) = k(k? 1)( k?2 ) = ( k? 1)
3
+ (?1)
3
( k? 1)。
假设对 nυ = 的所有圈，定理结论都成立。考虑顶点数 () nυ = +G1的圈 G。
从 G 中任取一条边 e，显然 G?e 是一个 n+1 阶树。 由定理 6.3.6,
11
(,)(1) (1)
nn
PG ek kk kk
+?
=? =?。
此外,G?e 是 n 阶圈，由归纳假设,(,) ( 1) ( 1) ( 1)
nn
PG ek k k? =?+。 再由定理 6.3.2,
16
(,) (,) (,)PGk PG ek PG ek= (1)
n
kk=? [( 1) ( 1) ( 1)]
nn
kk+
= (1) (1)(1)
11nn
kk
++
+ = (1)(1)(1)kk
υυ
+ 。
证毕。
本节最后，我们列举关于色多项式的几个未解决的问题。
1,色多项式与图不是一一对应的。虽然同构的图有相同的色多项式，但色多项式相同的两个图未必同构。例如，所有 υ个顶点的树都有相同的色多项式，但并非所有 υ阶树都是同构的。
问题 1,有相同色多项式的图有什么共同特点？
2,满足定理 6.3.4 的多项式未必就是色多项式。 例如,多项式
432
33kkk?+满足定理 6.3.4，
但它不是任何图的色多项式。事实上，假如它是某个图 G 的色多项式，则
（ 1）若 G 连通，因,ε υ==34，故 G 应是一个树，其色多项式应为
34 3 2
(1) (1) 3 3kk kk k k k
υ?
=?≠?+
1
。
（ 2）若 G 不连通，则因它有 4 个顶点 3 条边，故只能是
31
GK K= ∪ 。而此时
432
31
(,) (,) (,) ( 1)( 2) 3 3PGk PK k PK k kk k k k k k=?=≠?+。
问题 2,如何判断一个多项式是色多项式？
3,Read 猜想：色多项式 P(G,k)的系数的绝对值总是先严格单调递增，然后严格单调递减。
问题 3,证明或否定这一猜想。
4,问题 4,设计求色多项式的更好的算法。
注,求图的色多项式的有效算法将给出求图的点色数的有效算法，因此，确定图的色多项式的问题是一个 NPC 问题。
有关色多项式的更多内容可参看 [7],[8],[ 9]或 [10]。
[7] D.B,West,Introduction to Graph Theory (second edition),Prentice-Hall,Inc.,2001,（中译本：李建中、骆吉周译，图论导引，机械工业出版社,2006） 。
[8] W.T,Tutte,Graph Theory,Cambridge University Press,2001,
[9] R.C,Read and W.T,Tutte,Chromatic polynomials,Selected Topics in Graph Theory 3,
(eds,L,W,Beineke,and R.J,Wilson),Academic Press,New York,(1988) 15-42,
[10] D,Reinhard,Graph Theory (second edition),Springer-Verlag New York,2000,
17
§ 6.4 完美图
在 6.2 节，我们得到色数的一个下界,(G) (G)χ ω≥,其中 (G)ω 表示图 G 的团数。
有一些图的色数能达到这个下界，比如完全图和二部图。如果一个图的任何导出子图的色数都能达到这种下界，则称这个图为完美图。完美图的正式定义如下。
定义 6.4.1 若图 G 的每个点导出子图 H 都有 (H) (H)χ ω=,则称 G 为 完美图 。
容易验证，完全图及完全图的补图（空图）都是完美图。
定理 6.4.1 （ 1） 2n ≥ 时，偶圈
2n
C 及其补图都是完美图；
（ 2） 2n ≥ 时，奇圈
21n
C
+
及其补图都不是完美图；
证明,（ 1） 2n ≥ 时，偶圈
2n
C 的色数和团数都是 2。而且,C
2n
除自身外的任何导出子图 H
是一些路的不交并（可能会有孤立顶点） 。如果 H 不全是孤立顶点，则其色数和团数都是 2；
如果全是孤立顶点，则色数和团数都是 1。因此
2n
C 是完美图。
对
2n
C 的补图
2n
C,因其中任何 3 点都不是独立集，对其顶点正常染色时每个色类（染同一色的顶点集合） 不超过 2 个顶点,因此
2n
C 的顶点正常染色至少需要 n 种色。 另一方面，
设沿着圈
2n
C 顶点依次为
12 2
,,,
n
vv vnull,
2n
C 中对
12
,vv染同一种色，
34
,vv染同一种色，…，
21 2
,
nn
vv
染同一种色，则获得
2n
C 的一种顶点正常 n 染色，可见
2
()
n
Cnχ = 。其次，所有奇数下标的点在
2n
C 中彼此互不相邻,从而构成
2n
C 的一个 n 点团。 因此
22
() ()
nn
CnCωχ≥= 。
另一方面，由色数的下界
22
() ()
nn
CCχω≥,便知
22
() ()
nn
CCχω= 。
对
2n
C 的任一个异于
2n
C 的导出子图 H，设其顶点下标（按
2n
C 上的标号）由小到大依次为
12
,,,,
k
ii i
vv vnull ( 2kn< ),这些顶点在
2n
C 上导出的子图 H′是一些路及一些孤立顶点的不交并。设这些路中有 r
1
条含有偶数个顶点,r
2
条含有奇数个顶点，另有 r
3
个孤立顶点。
对每条路，取其一个端点作为起始点，依次对路上的点交替标上奇偶标号。并从起始边开始间隔取边作为匹配边,这样可得到 H′的一个最大匹配。 设该最大匹配有 r 对点 （即 r 条边）,
则这 r 对顶点的每一对在 H 中互不相邻，可染同一种色。又因 H 中任何三点都不构成独立集，故 (H) ( 2 )rk rkrχ =+? =?。另一方面，取上述各条路上所有奇标号的顶点，与 H′的所有孤立点组成顶点子集 A，则 A 是 H′的最大独立集，从而是 HH′= 的最大团。因为在含有偶数个顶点的路上，奇标号顶点的个数与匹配边的个数相等，而在每条含有奇数个顶点的路上，奇标号顶点的个数比匹配边的个数多 1，因此 |A| = r + r
2
+ r
3
。因 r
2
+ r
3
是各条含有奇数个顶点的路上未被匹配的点数与 H′中孤立顶点个数之和，故 r
2
+ r
3
= k? 2r。从 而 |A| =
r + (k?2r) = k? r。由此可见 (H) | A | (H)krω χ= =?= 。因此
2n
C 是完美图。
18
（ 2） 2n ≥ 时，奇圈
21n
C
+
的色数是 3，团数是 2，因此不是完美图。
对
21n
C
+
的补图
21n
C
+
,因其中任何 3 点都不是独立集,对其顶点正常染色时每个色类 （染同一色的顶点集合）不超过 2 个顶点，因此
21n
C
+
的顶点正常染色至少需要 n+1 种色。另一方面，设沿着圈
21n
C
+
顶点依次为
12 21
,,,
n
vv v
+
null,
21n
C
+
中对
12
,vv染同一种色，
34
,vv染同一种色，…，
21 2
,
nn
vv
染同一种色，最后给
21n
v
+
染一种色，则获得
21n
C
+
的一种顶点正常
n+1 染色，可见
21
() 1
n
Cnχ
+
=+。其次，考虑
21n
C
+
的最大团。因
i
v 与
1i
v
+
在
21n
C
+
中不相邻
（ 1,2,,2in= null ）,且
21n
v
+
与 v
1
也不相邻，故从
12 21
,,,
n
vv v
+
null 中最多能取出 n 个在
21n
C
+
中彼此相邻的点,即
21n
C
+
的最大团含点数不超过 n 个。 因此
21 21
() 1()
nn
Cnn Cωχ
++
≤<+= 。
这表明
21n
C
+
不是完美图。
定理 6.4.2 任何二部图及二部图的补图都是完美图。
证明：因为二部图的色数和团数都为 2，且其任何一个导出子图仍为二部图，故二部图都是完美图。下证二部图的补图是完美图。
设 G 是一个二部图，对补图 G 的任一个子图 G′，它必定是 G 的某个子图 H 的补图，
即 HG，使 GH′= 。下面只需证明 (H)= (H)χω即可。
用 (H)α 和 (H)β′ 分别表示 H 的独立数和边覆盖数，则 (H)= (H)ωα，且由推论 5.2.2，
(H)= (H)α β′ 。另一方面，设 (H) kχ =,{
12
,,,
k
VV Vnull }是 H 的一个顶点正常 k 染色，则每个
i
V 是 H 的一个团。由于二部图 H 中无三角形,H 的团要么只有１个点，要么只有两个点。因此，各个
i
V 在 H 中的导出子图合在一起形成了 H 的一个匹配 M 和一些 M 未饱和点。
由于 {
12
,,,
k
VV Vnull }是 H 的顶点正常染色的最小色类划分，故 M 是 H 的最大匹配。由推论
5.2.1,(H)=|M|+β′ M 未饱和点的个数＝ k。
因此,(H)= (H)= (H) (H)kωαβ χ′ == 。证毕。
设 G 是一个图。 G 的 线图 (line graph)L(G)是以 G 的边集作为顶点集的图,L(G)中两顶点相邻当且仅当相应的两条边在 G 中相邻。
线图的性质已得到较好的研究，读者可参看 [11]或 [12]
[11] F,Harary,Graph Theory,Addison-Wesley,Reading,Mass.,1969.(中译本,李慰萱译,图论，
上海科技出版社,1980),
[12] R.L,Hemminger,and L,W,Beineke,Line graphs and line digraphs,Selected Topics in Graph
Theory (L,W,Beineke,and R.J,Wilson editors),Academic Press,London,(1983),271-306,
值得注意的是,G 的线图 L(G)中的一个团与 G 中的一个顶点及其关联边对应，该团含的顶点数等于 G 中对应顶点的度。 L(G)中的一个独立集与 G 中的一个匹配相对应,L(G)的独立数等于 G 的边覆盖数（即最大匹配所含的边数） 。 L(G)的点正常染色对应于 G 的边正常染色，故 (L(G)) (G)χ χ′= 。
19
定理 6.4.3 设 G 是二部图，则 G 的线图 L(G)及其补图 L(G) 都是完美图。
证明：因 (L(G))ω 等于 G 的顶点最大度 (G)Δ,而 (L(G)) (G)χ χ′= 。 G 是二部图，由定理 6.1.1,(G) (G)χ′ =Δ,从而 (L(G)) (L(G))χ ω= 。由于 L(G)的点导出子图对应于 G
的边导出子图，而二部图的边导出子图仍是二部图，故上述推导对 L(G)的所有点导出子图都成立，因此 L(G)是完美图。
下面考虑线图 L(G)的补图 L(G) 的完美性。设 (L(G)) kχ =,
12
{,,}
k
VV Vnull 是 L(G) 的一个顶点 k 正常染色。每个
i
V 是 L(G) 的一个独立集，即 L(G)的一个团，它对应于 G 中某个顶点（记为 v
i
）关联的所有边
i
E,(1,2,,)ik= null 。因
12
(( ))
k
VV VVLG=∪∪null∪,故
12
EE EE()
k
G=∪∪null∪,这表明
12
{,,,}
k
vv vnull 是 G 的一个点覆盖集，而且 (L(G)) kχ =
保证了它是 G 的一个最小点覆盖，因此,(L(G)) (G)kχβ== 。另一方面,(L(G))ω 等于 L(G) 中最大点独立集含的顶点数，进而等于 G 中最大匹配所含的边数，即
(L(G))ω (G)α′= 。 由 K?nig-Egerváry 定理 （定理 5.2.2）,对于二部图 G,有 )()( GG βα =′,
因此 (L(G))χ = (L(G))ω 。因 L(G) 的点导出子图必是 L(G)的相应点导出子图的补图，它对应于 G 的一个边导出子图，而二部图的边导出子图仍是二部图，故上述推导对 L(G) 的所有点导出子图都成立，因此 L(G) 是完美图。证毕。
以上完美图和非完美图的个例都支持一个普遍性的命题,一个图是完美图当且仅当它的补图是完美图。这个命题称为 完美图猜想,由 Berge 于 1961 年提出。许多人认为要证明这个猜想是很困难的。 1972 年,22 岁的 Lovász 证明了这个著名的猜想，在当时引起了组合数学界的轰动。下面我们来介绍对完美图猜想的证明。
引理 1 图 G 是完美图当且仅当对 G 的每个点导出子图 H，存在一个独立集 I，使得
(H I) (H)ω ω?< 。即 G 是完美图当且仅当 G 的每个点导出子图 H 都有一个独立集 I，它与 H 的所有最大团都有公共顶点。
证明：必要性。设 G 是完美图,H 是 G 的一个点导出子图，则 (H) (H)χ ω= 。设
(H) kχ = 。在 H 的任何一种顶点 k 正常染色下，设 I 是一个色类（染某种色的所有顶点之集） 。则有
(H I) (H I) 1 (H) 1 (H) 1 (H)kω χχωω? ≤?=?=?=?< 。
充分性：对 (G)ω 作归纳法。
当 (G)ω =1 时,G 显然是完美图。
假定对满足定理条件且 (G) kω < 的任何图 G,G 都是完美图。
设 G 是一个使得 (G) kω = 的图，且对 G 的每个点导出子图 H，存在一个独立集 I，使得 (H I) (H)ω ω?< 。由归纳假设,HI? 是完美图，于是 (H I) (H I)χ ω? =?。设
(H I) rχ?=且
12
{,,,}
r
VV Vnull 是 HI? 的一个顶点正常 r 染色。则
12
{,,,,I}
r
VV Vnull 是 H 的一个顶点正常 r+1 染色。故 (H) 1 (H I) 1 (H I) 1 (H)rχ χωω≤ +=? +=? +≤ 。另一方面,(H) (H)χ ω≥ 。因此 (H) (H)χ ω= 。这表明 G 是完美图。归纳完成。证毕。
20
设 G 是一个图，其顶点集为
12
{,,,}
n
vv vnull,
12
H,H,,H
n
null 是一些无公共顶点的图。
将 G 中每个顶点
i
v 用
i
H 替换 (1,2,,)in= null,并按 G 中顶点的相邻关系连接
12
H,H,,H
n
null,如果
i
v 与
j
v 在 G 中相邻，则将 H
i
的顶点与 H
j
的顶点之间建立完全连接。
这样得到的图称为
12
H,H,,H
n
null 在 G 上的 合成图,记为 G{
12
H,H,,H
n
null }。确切地说，
G{
12
H,H,,H
n
null }的顶点集为
12
V(H ) V(H ) V(H )
n
∪∪null∪,对 G{
12
H,H,,H
n
null }中任意两顶点 u,v，当且仅当 u 和 v 在某个 H
i
中相邻，或者 u 和 v 分别属于 H
i
和 H
j
且相应的
i
v 和
j
v 在 G 中相邻时,u,v 在 G{
12
H,H,,H
n
null }中相邻。
引理 2,若 G 和
12
H,H,,H
n
null 都是完美图，则合成图 G{
12
H,H,,H
n
null }也是完美图。
证明,由于合成 G{
12
H,H,,H
n
null }可以看成是用
12
H,H,,H
n
null 逐次替换
12
,,,
n
vv vnull
得到的，因此只需证明用一个完美图 H 替换 G 的某一个顶点 v 得到的图 G{H} 是完美图即可。按照引理 1，完美图 H 有一个点独立集 I 使得 (H I) (H)ω ω? < 。用 (G)χ 种颜色对 G
的顶点进行正常染色，将 v 及与 v 同色的顶点的集合记为 A，则 B(IA){}v=?∪ 是 G{H}
的一个独立集。我们断言 B 与 G{H}的每个最大团都有公共顶点。
事实上，设 Q 是 G{H}的一个最大团。如果 Q 含有 H 中的顶点，则因在 G{H}中 H 的各个顶点对 H 外的相邻关系是相同的，故此时 H 中每个顶点都与 QH? 的所有顶点相邻。
因此 Q 必定含有 H 的一个最大团。又因 (H I) (H)ω ω? <,H 的每个最大团都与 I 有公共顶点，从而 Q 必定与 I 有公共顶点，于是 B(IA){}v=?∪ 与最大团 Q 有公共顶点。
如果 G{H}的最大团 Q 不含有 H 中的顶点,则 QV(G){}v且在 G 中 v 不与 Q 的顶点相邻，因此 Q 是 G 的一个最大团。因 G 是完美图,(G) (G)χ ω=,且对 G 的任何一种
(G)χ 正常染色，每个色类（同色顶点之集）至多含最大团 Q 中一个点，而
|Q| (G) (G)ω χ==，于是每个色类恰含 Q 中一个点。 因此在 G 的任何一种 (G)χ 正常染色下,Q 与每个色类都有公共点。特别地,Q 与前述色类 A 有公共点，从而与 IA∪ 由公共点，又因为 Q 不含顶点 v，故 Q 与集合 B(IA){}v=?∪ 有公共点。
对 G{H}的任一个点导出子图 G′，如果 GG′? 或 GH′?,则因完美图的子图仍是完美图，故由引理 1,G′有一个独立集，它与 G′的所有最大团都有公共顶点。否则,G′可视为由 G 的某个含 v 的点导出子图与 H 的某个点导出子图在 v 点合成的图，按上述推导,G′
也存在独立集，它与 G′的所有最大团都有公共顶点。
由以上结果可见，图 G{H}满足引理 1 的条件，故是完美图。证毕。
定理 6.4.4 (完美图定理,Lovász
[13],[14]
,Fulkerson
[15]
,1971) 一个图是完美图当且仅当它的补图是完美图。
[13] L,Lovász,Normal hypergraphs and the perfect graph conjecture,Discrete Mathematics,
2(1972),253-267,
[14] L,Lovász,A characterization of perfect graphs,J,Comb,Theory (B),13(1972),95-98,
[15] D.R,Fulkerson,Blocking and anti-blocking pairs of polyhedra,Math,Programming,1(1971),
168-194,
21
证明,必要性,设 G 是完美图。为证其补图 G 也是完美图，由引理 1，只需证明对 G 的任何点导出子图 H,都有一个独立集 I，使 得 (H I) (H)ωω?< 。将 H 的补图记为 H，它 是 H
的顶点在 G 中的导出子图。从 H 的角度来看，需要证明的就是，存在 H 的一个团 Q，使得
(H Q) (H)α α?< 。我们用反证法来证明这一结论。
设 H 的顶点集为
12
{,,,}vv v
υ
null,
12
Q,Q,,Q
r
null 是 H 的全部团。假定对每个 Q
i
，都存在 HQ
i
的某个点独立集
i
A,使得 || (H)
i
A α=,( 1,2,,ir= null )。 对 H 的任一个顶点 v
k
,设
12
,,,
r
AA Anull 中有
k
n 个含有 v
k
，用
k
n 阶完全图
k
n
K 替代 H 中的顶点 v
k
,（ 1,2,,k υ= null ）,
则得到合成图 G′=H{
12
,,,
nn n
KK K
υ
null }。由于完美图 G 的子图 H 是完美图，完全图也是完美图，按照引理 2,G′是完美图。下面来计算 (G )ω ′ 和 (G )χ ′ 。
G′的最大团必可由 H 的某个团 Q
j
的顶点用相应的完全图替代后获得，因此，
j
(G )
k
k
vQ
nω
∈
′ =
∑
。注意
k
n 是 r 个独立集
12
,,,
r
AA Anull 含有顶点
k
v 的独立集的个数。对
1,2,,ir= null,因 A
i
是独立集而 Q
j
是团，故每个 A
i
至多含有 Q
j
中一个顶点。也就是说，对
Q
j
中任何两个顶点
k
v
′
和
k
v
′′
,这 r 个独立集中含有
k
v
′
的独立集和含有
k
v
′′
的独立集互不相同。
此外，与 Q
j
对应的独立集 A
j
不含有 Q
j
中任何顶点。因此，含有 Q
j
中各个顶点的独立集个数之和不会大于 1r?,即
(G )
ki
k
vQ
nω
∈
′ =
∑
1r≤? 。 (1)
另一方面，设 (G ) tχ ′ =,
12
,,,
t
VV Vnull 是 G′的一个顶点 t 正常染色，则
12
(G ) | | | | | | (G ) (G )
t
VV Vυ χα′′′=+ ++≤?null 。 (2)
由 G′的构造可知,(G ) (G)α α′ = 。 (3)
且由
12
,,,
r
AA Anull 的性质，有
1
|| (G)
r
i
i
Arα
=
=?
∑
。 (4)
构造矩阵 M ()
ij
m=,其中
ij
m 当 A
i
含有 H 的顶点 v
j
时取值为 1,否则取值为 0,( 12ir= null，，；
1,2,,( )j Hυ= null ),注意到
1
||
r
i
i
A
=
∑
等于将矩阵 M 的元素按行相加，而将 M 的元素按列相加的结果等于
()
1
()
H
j
j
nG
υ
υ
=
′=
∑
。因此，
1
|| (G)
r
i
i
A υ
=
′=
∑
。结合 (2),(3),(4)式有,
(G ) (G ) (G )χ αυ′′ ′?≥
1
|| (G) (G)
r
i
i
Ar rαα
=
′==?=?
∑
。
即 (G ) rχ ′ ≥,与 (1)式结合，得 (G ) (G )χ ω′ ′> 。这与 G′的完美性矛盾。必要性得证。
充分性,设 G 是完美图，则因 G 是 G 的补图，故由必要性的证明，知 G 也是完美图。
证毕。
在历史上，人们曾定义了两种完美图。为了给出第二种完美图的定义，我们需要引入团覆盖集的概念。
22
设 G 是一个图,F
12
{,,,}
r
QQ Q= null 是 G 的一些团的集合，如果
12
()
r
QQ QVG=∪∪null∪,则称 F 是 G 的一个 团覆盖集 。 G 的含团数最少的团覆盖集称为最小团覆盖集，它所含的团的个数称为 G 的 团覆盖数,记为 (G)θ 。
设 F
12
{,,,}
r
QQ Q= null 是简单图 G 的任一个团覆盖,I 是 G 的任一个点独立集。因 F 是团覆盖，对 I 的任意一点 v,必存在某个团
i
Q,使
i
vQ∈,而 I 中任意两点不会属于同一个团，因此 |I| |F|r≤=,由此可知 (G)θ (G)α≥ 。
定义 6.4.2 若图 G 的每个点导出子图 H 都有 (H) (H)α θ=,则称 G 为关于点独立数的完美图，简称为 α -完美图 。
相应地，我们将定义 6.4.1 中的完美图称为关于色数的完美图，简称为 χ -完美图。下面的定理表明这两种完美图的定义本质上是相同的。
定理 6.4.5 图 G 是 α -完美图当且仅当它是 χ -完美图。
证明：首先证明 G 是 α -完美图当且仅当其补图 G 是 χ -完美图。
事实上,G 的每个点导出子图 H 必是 G 的某个点导出子图 H 的补图 。若 G 是 α -完美图，则 G 有 (H) (H)α θ= 。设 (H) kχ =,
12
,,,
k
VV Vnull 是 H 的一个顶点 k 正常染色，
则
12
,,,
k
VV Vnull 构成 H 的一个最小团覆盖。因此 (H) (H)χθ= 。此外,H 的最大独立集必为 H 的最大团，故 (H) (H)αω= 。从而 (H) (H) (H) (H)χθαω===。这表明 G 是 χ -
完美图。
反之，若 G 的补图 G 是 χ -完美图，则对 G 的任一个点导出子图 H,(H) (H)χω= 。
与前面完全同样的道理，得 (H) (H)χθ= 及 (H) (H)αω= 。因此,
(H) (H)αω= (H) (H)χθ==。
这表明 G 是 α -完美图。
其次，由完美图定理（定理 6.4.4）,G 是 χ -完美图当且仅当 G 是 χ -完美图。从而定理得证。
目前，人们已经发现近百种完美图
[16]
。其中除了前面介绍的一些外，还有区间图和弦图也是较常见的两种。
[16] http://www.cs.rytgers.edu/~chvatal/perfect/spgt.html
设
12
,,
n
JJ Jnull 是 n 个实数区间,以 {
12
,,
n
JJ Jnull }为顶点集构造图 G,G 中顶点
i
J 与
j
J
相邻当且仅当区间
i
J 与
j
J 相交。这样得到的图称为 区间图 (interval graph)。
设 C 是一个圈,C 的一条 弦 是本身不在 C 上但两端点在 C 上的边。如果图 G 中每个长至少为 4 的圈都有弦，则称 G 为 弦图 （ chordal graph） 。
23
定理 6.4.6 区间图是完美图。
证明,设 G 是一个区间图，按 G 的顶点对应区间的左端点值由小到大对 G 的所有顶点排序，设顺序为
12
,,,vv v
υ
null 。依次对 G 的顶点染色：对顶点
i
v,用此前
i
v 的邻点尚未使用的最小色号的颜色给
i
v 染色,（ 1,2,,i υ= null ） 。这样可得到 G 的一个顶点正常染色。设这样染色后用到的最大色号为 k，假定顶点
j
v 染有颜色 k，这说明在给
j
v 染色时，已经至少有
j
v
的 k?1 个下标小于 j 的邻点分别染有颜色 1 到 k?1。设
j
v 对应的区间
j
J 的左端点为 x，则上述 k?1 个顶点对应的区间都与
j
J 相交且左端点小于和等于 x，因而这些区间必定彼此相交。
由此可知这 k 个顶点构成 G 的一个 k-团。从而 (G) (G)kχ ω≤ ≤ 。另一方面，对任何图都有 (G) (G)χ ω≥,故 (G) (G)χ ω= 。
由于区间图 G 的点导出子图 H 仍是区间图,故对 H 上述推导仍成立。 因此 G 是完美图。
证毕。
与定理 6.4.6 类似可证，弦图也是完美图（见 [7] p181） 。
含有奇圈的无三角形图，由于其团数为 2，色数至少是 3，故不是完美图。按照完美图定理，这样的图的补图也不是完美图。这就是说，若 G 是完美图，则 G 和 G 的任何导出子图必定不含有长至少是 5 的奇圈。 Berge 猜想，这个命题的逆命题也是成立的，这便是著名的强完美图猜想。
强完美图猜想 （ Berge
[17]
,1961） G 是完美图当且仅当 G 和 G 的任何导出子图都不是长至少为 5 的奇圈。
[17] C,Berge,F?rbung von Graphen deren s?mtliche bzw,Deren ungerade Kreise starr sind
(Zusammenfassung),Wissenschaftliche Zeitschrift,Martin Luther Universit?t Halle-Wittenberg，
Mathematisch-Naturwissenschaftliche Reihe,(1961),114-115,
经过人们四十年的努力，强完美图猜想终于在 2002 年被 Chudnovsky 等人所证明
[16][18][19]
。此外，判别一个图是否为完美图的多项式时间算法也已被得到
[20],[21]
。这是完美图理论的重大进展。通过围绕完美图猜想和强完美图猜想的研究，完美图理论已经形成了十分丰富的内容，加深了人们对图的结构性质的认识。目前这一领域的研究仍很活跃。
有关完美图的更多内容可参看文献 [7],[16]或 [22]~[27]。
关于染色问题可进一步参考文献 [28]~[64]。
[18] M,Chudnovsky,N,Robertson,P,Seymour,R,Thomas,Progress on perfect graphs,
Mathematical Programming Ser.B,97(2003)405-422,
[19] M,Chudnovsky,N,Robertson,P,Seymour,R,Thomas,The strong perfect graph theorem,
Annals of Mathematics,164:1(2006) 51-229,
[20] M,Chudnovsky,G,Cornuéjols,X,Liu,P,Seymour,K,Vu?kovi?,,Recognizing Berge graphs,
Combinatorica,25(2005),143-186,
[21] G,Cornuéjols,X,Liu,and K,Vu?kovi?,A polynomial algorithm for recognizing perfect
24
graphs,Proceeding of 44
th
FOCS (2003) 20-27,
[22] M.C,Golumbic,Algorithmic Graph Theory and Perfect Graphs,Academic Press,1980
[23] L,Lovász,Perfect graphs,in Selected Topics in Graph Theory II (L.W,Beineke,and R.J,
Wilson eds.),Academic Press,London,(1983),55-87,
[24] C,Berge,and V,Chvátal,Topics on Perfect Graphs,Ann,Discr,Math,21,North Holland,
1984,
[25]A,Schrijver,Combinatorial Optimization Polyhedra and Efficiency,New York,NY,
Springer-Verlag,2003,
[26] J.L,Ramírez Alfonsín,and B.A,Reed,Perfect graphs,J,Wiley and Sons,Chichester,2001,
[27] G,Cornuéjols,The strong perfect graph conjecture,Proceedings of the ICM,Beijing,China,
2002,
[28] Tommy R,Jensen and Bjarne Toft,Graph Coloring Problems,Wiley-Interscience,New York,
1995,
[29] B,Toft,75 graph-colouring problems,in Graph Colourings (R,Nelson and R.J,Wilson,Eds.),
Wiley,New York,(1990),9-35,
[30] http://www.nada.kth.se/~viggo/problemlist/
[31] http://web.cs.ualberta.ca/~joe/Coloring/#Links.other
[32] N,Alon,Restricted colorings of graphs,in Surveys in Combinatorics 1993 (Proc,14
th
British
Combinatorial Conference),Cambridge Univ,Press,Cambridge,(1993),1-33,
[33] H.R,Hind,Restricted Edge-Colourings,Ph.D,thesis,University of Cambridge,1988,
[34] Reinhard Diestel,Graph Theory,Springer,1997,
[35] N,Rorbertson,P,D,Seymour and R,Thomas,Tutte’s edge-coloring conjecture,J,Combin,
Theory Ser,B,70(1997),166-183,
[36] M,O,Albertson,A,V,Kostochka,and D,B,West,Precoloring Extensions of Brooks'
Theorem,SIAM J,Discrete Math.,18(2004-2005),542-553,
[37] L.D,Andersen,On edge-colourings of graphs,Math,Scand,40(1977),161-175,
[38] J,Janssen and K,Kilakos,Bounded Stable Sets,Polytopes and Colorings,SIAM J,Discrete
Math.,12(1999),262-275,
[39] N,Alon and M,Krivelevich,Testing k-colorability,SIAM J,Discrete Math.,15(2001-2002),
211-227,
[40] J,Fiala,K,Jansen,V,B,Le,and E,Seidel,Graph Subcolorings,Complexity and Algorithms,
SIAM J,Discrete Math.,16(2002-2003),635-650,
[41] 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) 361-376,
[42] D,Král',Coloring Powers of Chordal Graphs,SIAM J,Discrete Math.,18(2004-2005),
451-461,
[43] G,Agnarsson and M,M,Halldórsson,Coloring Powers of Planar Graphs,SIAM J,Discrete
Math.,16(2002-2003),651-662,
[44] Cécile Murat and Vangelis Th,Paschos,On the probabilistic minimum coloring and
25
minimum k-coloring,Discrete Applied Mathematics,154(2006),564-586,
[45] G,Chartrand,L,Nebesky and P,Zhang,Hamiltonian colorings of graphs,Discrete Applied
Mathematics,146(2005),257-272
[46] V,Guruswami and S,Khanna,On the Hardness of 4-Coloring a 3-Colorable Graph,SIAM J,
Discrete Math.,18(2004-2005),30-40,
[47] 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),385-411,
[48] H,Enomoto,M,Hornák,and S,Jendrol',Cyclic Chromatic Number of 3-Connected Plane
Graphs,SIAM J,Discrete Math.,14(2001),121-137,
[49] Oleg V,Borodin and Douglas R,Woodall,Cyclic Colorings of 3-Polytopes with Large
Maximum Face Size,SIAM J,Discrete Math.,15(2001-2002),143-154,
[50] V,A,Bojarshinov,Edge and total coloring of interval graphs,Discrete Applied Mathematics,
114(2001),23-28,
[51] O.V,Borodin,On the total coloring of planar graphs,J,Reine Angew,Math.,394(1989),
180-185,
[52] 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),17-20,
[53] Celina M.H,de Figueiredo,J,Meidanis,C,P,De Mello,Total-Chromatic number and
chromatic index of dually chordal graphs,Information Processing Letters,70(1999),147-152,
[54] A,Daneshgar and H,Hajiabolhassan,Unique list-colourability and the fixing chromatic
number of graphs,Discrete Applied Mathematics,152(2005),123-138
[55] O.V,Borodin and A.V,Kostochka,List edge and list total colorings of multigraphs,Journal
of Combinatorial Theory,(Ser,B),71(1997),184-204,
[56] F,Galvin,The list chromatic index of a bipartite multigraph,Journal of Combinatorial
Theory,(Ser,B),63(1995),153-158,
[57] J,Kahn,Asymptotically good list-colorings,J,Combin,Theory Ser,A,73(1996),1-59,
[58] M,R,Salavatipour,On sum coloring of graphs,Discrete Applied Mathematics,127(2003),
477-488,
[59] M,Larsen,J,Propp,and D,Ullman,The fractional chromatic number of Mycielski’s graphs,
J,Graph,Theory,19(1995),411-416,
[60] U,Feige,M,Langberg,and G,Schechtman,Graphs with Tiny Vector Chromatic Numbers
and Huge Chromatic Numbers,SIAM J,Computing,33(2003-2004),1338-1368
[61] S,Gerke,Weighted colouring and channel assignment,DPhil thesis,University of Oxford,
2000,
[62] C,Mcdiarmid,and B,Reed,Channel assignment and weighted colouring,Networks,36(2000)
114-117,
[63] C,Nomikos,A,Pagourtzis and S,Zachos,Routing and path multicoloring,Information
Processing Letters,80(2001) 249-256,
[64] 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),1040-1049,
26
第六章习题
1,证明 n ≠ 0 时,(1)
21
(K )
n
χ
+
′ =2n+1=
21
()
n
K
+
Δ ； (2)
2
()
n
Kχ′ =2n－ 1=
2
()
n
KΔ 。
2,找出一个适当的边染色以证明 )()(
,,nmnm
KK Δ=′χ 。
3,轮图
1,n
W 是由一个点与长为 n 的圈上所有顶点相连形成的图，证明：若 n ≥4，则
1,1,
() ()
nn
WWχ′ =Δ = n。
4．证明：对 Petersen 图 G,(G) 4χ′ = 。
5,（ 1）证明：对于最大度为 Δ 的任何二部图 G，存在着包含 G 的 Δ 正则简单二部图。
（ 2）若 G 是最大度为 Δ 的无环图，则存在 Δ 正则图以 G 为子图。
6．试用 ε 和 (G)α′ 给出 (G)χ′ 的一个下界。
7,设 G 是一个无环边的图,3)( =Δ G 且 G 包含一个生成二部子图 H，使得 ()vVG?∈,
1
() ()
2
HG
dv dv≥,则 4)( ≤′ Gχ 。
8,设 G 是二部图，且 0)( >Gδ,证明：图 G 有一种 )(Gδ 边染色，使得所有的色都在 G
的每个顶点上出现。
9,证明：每个 3 正则 Hamilton 图都有正常 3 边着色。
10,证明：对任何图 G，
3
(G) (G)
2
χ′ ≤Δ 。
11.证明,(1)若 G 是无环简单图，且 () 2 1,() ()Gn GnGυ ε= +>Δ，则 1)()( +Δ=′ GGχ 。
(2) 利用上述结果证明,
(a) 若 G 是一个由顶点数为偶数的无环正则简单图剖分一边后所得之图，则
1)()( +Δ=′ GGχ ；
(b) 若 G 是一个由顶点数为奇数的无环 k－正则简单图去掉少于
2
k
条边后得到的图，则
1)()( +Δ=′ GGχ 。
12,证明：若 G 是非空正则简单图，且 ()Gυ 为奇数，则 1)()( +Δ=′ GGχ 。
13,证明：若 G 是有割点的正则简单图，则 1)()( +Δ=′ GGχ 。
14,设图 G 的边独立数是 (G)α′ 。证明：如果 (G) (G) (G)ε α′>Δ,则 G 是第二类图。利用此结果证明：如果 (G) (G)
2
υ
ε
>Δ?
，则图 G 是第二类图。
15,证明：对不是奇圈的连通图，如果它的所有圈有相同的奇偶性，则 (G) (G)χ′ =Δ 。
27
16,设 G 为 υ阶简单图,证明,若 G 中恰有一个点的度达到 1υ?,则 (G) (G) 1χ υ′ =Δ =? 。
17,证明或否定：如果 G
1
和 G
2
是第一类图，且
12
GHG，则 H 是第一类图。
18,设 G 是简单图,x 与 y 是 G 中两个不相邻的顶点,π 是 G 的一个正常 k 边染色。证明：
若在该染色下 x,y 以及 x 的所有邻点均有颜色未在其上体现,则 G xy+ 也可 k 边正常染色。
19,利用上题的结果证明 Vizing 定理。并证明：若无孤立点的简单图 G 恰有一个度为 (G)Δ
的顶点，或 G 恰有两个度为 (G)Δ 的顶点但这两个顶点相邻，则 G 是第一类图，即
(G) (G)χ′ =Δ 。
20,求下列图的色数。
21,轮图
1,n
W 是由一个点与长为 n 的圈上所有顶点相连形成的图，
1,5
W 如下所示。证明
1,5
()4Wχ = 。
22,证明,
（1） 1)( =Gχ?
ν
KG = ；
（2） 2)( =Gχ?G 是非空二部图；
（3） )()( GG νχ =?
ν
KG? 。
（4）
3)(
12
=
+n
Cχ 。
（5） 3)( ≥Gχ? G 含有奇圈。
23,证明,
（1） G 是临界 1 色图?
1
G K? ；
（2） G 是临界 2 色图?
2
G K? ；
（3） G 是临界 3 色图?G 是奇圈；
（4） 任何 k 色图都包含临界 k 色子图；
（5） 每个色临界图都是连通的简单图。
24,下图是不是临界 3 色图？如果是，给出证明；如果不是，求出它的一个临界 3 色子图。
v
5
v
7
v
4
v
3
v
2
v
1
v
6
28
25,证明：下列 Gr?tzsch 图是临界 4 色图。
Gr?tzsch 图
26,设 H 是图 G 的子图，证明 (G) (H)χ χ≥ 。
27,设
12
,,,
k
GG Gnull 是图 G 的所有块，证明,() max{( )}
i
i
GGχ χ= 。
28,给出一个图 G 使得它有顶点 v 满足 ()()Gv Gχ χ? <,且 ()()Gv Gχχ?< 。
29,证明或否定：任何 k 色图 G 有一个正常 k 染色使得某个色类含 (G)α 个顶点。
30,证明或否定：对任何连通图 G，有
2
(G) 1
ε
χ
υ
≤+,（
2ε
υ
是图 G 的顶点平均度） 。
31,两个图 F 与 H 的并 FH∪ 是以图 F 和 H 的顶点集的并作为顶点集，且以 F 和 H 的边集的并作为边集形成的图。证明或否定：若 GFH= ∪,则 (G) (F) (H)χ χχ≤ + 。
32,设 G 和 H 不相交（即无公共点）,GH+ 表示 G 和 H 的 不交并 （即将 G 和 H 作为分支放在一起组成的图） 。证明 (G H) max{ (G),(H)}χ χχ+= 。
33,图 G 和 H 的 联 GH∨ 表示将 G 的每个顶点与 H 的每个顶点间都连边后形成的图。 证明
(G H) (G) (H)χ χχ∨= + 。
34,设 G 是完全图 K
r
与长为 5 的圈 C
5
的联：
5
G
r
CK= ∨,证明,(G) (G)χ ω> 。并证明 G 是一个色临界图。
35.设 I 是色临界图 G 的任一个点独立集，证明,(G I) (G) 1χ χ? =?。
36,证明：若 G 的任二奇圈都有公共顶点，则 5)( ≤Gχ 。
37,证明：若 G 的任二圈都没有公共顶点，则 () 3Gχ ≤ 。
38,证明：若 G 是简单图，则
2
2
()
2
G
υ
χ
υ ε
≥
。
39,证明：若 G 是二部图，则 (G) (G)χω= 。
40,证明：若 G 中最长奇圈的长度为 m ≥ 3，则 (G) 1mχ ≤ + 。
41,(1) 设简单图 G 的顶点集为
12
{,,,}vv v
υ
null,证明,如果每个
j
v 最多只与
12 1
{,,,}
j
vv v
null
29
中的 k 个顶点相邻（ 2 j υ≤≤）,则有 (G) 1kχ ≤ + ；
(2) 利用 (1)证明：对任何简单图 G 都有 (G) (G) 1χ ≤Δ+；
(3) 利用 (1)证明：对任何简单图 G 都有
H
(G) max (H) 1χ δ≤ +,其中 H 取遍 G 的所有点导出子图；
(4) 利用 (3)证明：若 G 是连通简单图但不是正则图，则 (G) (G)χ ≤ Δ ；
(5) 利用 (4)证明：若 G 是连通的正则简单图且含有 1 顶点割，则 (G) (G)χ ≤Δ ；
(6) 利用 (4)证明,若 G是连通的 k正则简单图 ( 3k ≥ ),且 G有 2顶点割,则 (G) (G)χ ≤Δ ；
(7) 利用上述结论证明 Brooks 定理：设 G 是连通简单图，且既不是奇圈也不是完全图，
则 (G) (G)χ ≤Δ 。
42,求下列两图的色多项式。
43,使用边的删除和收缩方法，并利用树和完全图的色多项式的结果，求 C
4
的色多项式。
44,证明,(,) ( 1) ( 1) ( 1)
nn
n
PC k k k=?+。
45,证明：若
1
HGK=∨，则 (,) (,1)PHk k PGk=。利用这一结果和上题结论证明：
对有 n 根辐条的轮图
1,n
W,
1,
(,) ( 2) ( 1) ( 2)
nn
n
PW k k k k k=?+。
46,利用树和 C
4
的色多项式结果，求下图的色多项式。
47,证明,（ 1）若图 G 含有 r 个孤立顶点，则色多项式 (,) (,)
r
PGk k PG k′=?,其中 G′是
G 去掉 r 个孤立顶点后所得的图； （ 2）若图 G 有重边和环边，用
1
G 表示 G 去掉重边和环边后所得的图，则
1
(,) (,)PGk PG k= 。
48,设 v 是图 G 的一个 1 度顶点，利用上题结论证明,(,) ( 1)(,)PG k k PG v k=。
49,设 G 是连通图，证明：
1
(,) ( 1)PGk kk
υ?
≤?。
50,证明：如果 G 至少含有一条边，则其色多项式的系数之和等于零。
51,证明,Petersen 图不是完美图。
