图论讲义第6章-图的着色问题

1 第六章 染色理论 许多实际问题可以归结为求图的匹配或者独立集。此外，在许多应用中，人们希望知道： 一个给定的图，它的边集至少能划分成多少个边不交的匹配？或它的顶点集至少能划分成多 少个点不交的独立集？这便是图的边染色和顶点染色问题。 §6.1 边染色 定义 6.1.1 非空无环图 G 的边正常 k 染色（proper edge k- colouring）是指 k 种颜色1 2 , k"，， 对 E(G)中元素的一种分配，使得相邻两条边所染颜色不同。换句话说，G 中边正常 k 染色 是映射 },,2,1{)(: kGEc "→ ， 使得对每个 i ( ki ,,2,1 "= ), )(1 ic− 是匹配或者空集。 注：若令 ),,2,1(},)()({)(1 kiiecGEeicEi "==∈== − ，则 G 的一个边正常 k 染色可看 成是边集的一种划分 ),,,( 21 kEEEc "= ，其中每个 Ei是匹配或空集。 例如，下面给出了 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 kEEEc "= 中每个 Ei 都是非空的 匹配。 （2）G 的边色数 )(Gχ ′ 是 G 中边不交匹配的最小数目。 （3） )(12)( 22 nn KnK Δ=−=′χ （因完全图 K2n有 2n-1 个边不交的匹配） （4） )()( GG Δ≥′χ 。（设 )()( Gvd Δ= ，则与 v 关联的 )(GΔ 条边至少需 )(GΔ 种色才 能正常染色）。 引理 6.1.1. 设 G 是非空无环的连通图，且不是奇圈，则存在 G 的边 2-染色，使得所用的两 种色在每个度 2≥ 的顶点处都出现。 证明：（1）设 G 是 Euler 图，则 G 中无奇度点。 若 G 本身是一个偶长度圈，则命题显然。若 G 不是一个偶长度圈，则 G 至少有一个顶 点 v0满足 4)( 0 ≥vd (否则，G 中所有顶点都是 2 度的，由于 G 连通，从而 G 是圈，由引理 条件，G 不是奇圈，故为偶圈，矛盾)。 3 3 4 1 1 3 22 31 1 2 4 2 2 3 2 1 1 2 2 设 02110 veevev ε" 是 G 的一条 Euler 闭迹。令 ieE i{1 = 为奇数}， ieE i{2 = 为偶数}。 于是 c = (E1, E2) 即为所求的边 2-染色。 需要说明的是，Euler 闭迹从度≥4 的顶点出发是必需的。例如在下图中，若从 2 度顶 点 u 处出发沿 Euler 闭迹交替地对边进行 2 染色，则 u 点可能仅能获得一种色（如图，1、2 表示两种颜色）。 (2) 设 G 不是 Euler 图。此时给 G 增添一个新顶点 v0，将 v0 与 G 的每个奇度顶点连一条 边，得到一个新图 G*。显然 G*的所有顶点都是偶数度的，因而是 Euler 图。设 0*)(2110 veevev Gε" 是 G*的一个 Euler 闭迹，令 ieE i{*1 = 为奇数}, ieE i{*2 = 为偶数}，这 样可得 G*的一个边 2-染色 ),( *2*1* EEc = ，（其中 0v 点的关联边有可能是同一种色）。按这 种办法给 G*的边染色后，去掉 0v 及其关联的边，便得到 G 的一个边 2-染色。对于 G 中偶 度点，它关联的边及其颜色与 G*中相同；对 G 的任何奇度点 v，在 G 中比在 G*中少关联一 条边，但只要 1)( >vdG , 便有 3)( ≥vdG , 故由染色的方法知，与 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 kEEEc "= 是 G 的一个最佳边 k 染色，且存在一个顶点 u 及两种颜色 i 和 j, 色 i 不在 u 处出现，而色 j 在 u 处出现了至少两次，则 ][ ji EEG ∪ 中含 u 的连通分支 必是奇圈。 证明：设 G1是 ][ ji EEG ∪ 中含 u 的连通分支。若 G1 不是奇圈，则由引理 6.1.1，G1有一个 边-2 染色，其两种色在 G1 中度 2≥ 的每个顶点处都出现。按这种染色办法用色 i 和 j 给 ji EE ∪ 中的边重新染色后，得到 G 的一个新的边 k-染色 ),,,( 21 kEEEc ′′′=′ " ，其中 i, j 两色都在 u 处出现，故 1)()( +=′ ucuc ,而对 u 之外的其它顶点 v，都有 )()( vcvc ≥′ 。于是 ∑∑ ∈∈ >′ )()( )()( GVvGVv vcvc 。这与 c 是最佳边 k-染色矛盾。证毕。 定理 6.1.1（König[1], 1916）设 G 是二部图，则 ( ) ( )G Gχ ′ = Δ 。 [1] D. König, Über Graphen und ihre Anwendung auf Determinantentheorie und mengenlehre, Math. Ann., 77(1916), 453-465. 证明（反证法）：假设 ( ) ( )G Gχ ′ ≠ Δ 。则由定义 6.1.3 的注（4）， ( ) ( )G Gχ ′ > Δ 。设 ),,,( 21 Δ= EEEc " 是 G 的一个最佳边Δ染色，则 c 必定不是正常染色。故存在顶点 u 满 足 )()( uduc < ，因而必有某两条在 u 点相邻的边染了同一种色。而且，因 ( ) ( )d u G≤ Δ , 故 u 1 2 1 2 1 1 2 3 Δ种色中必有某种色不在 u 上出现。显然 u 满足引理 6.1.2 的条件，因此 G 中有奇圈。这与 G 是二部图矛盾。证毕。 注：也可按推论 3.3.3，二部图的边集可分解为 )(GΔ 个边不交的匹配，故 ( ) ( )G Gχ ′ = Δ 。 定理 6.1.4 (Vizing 定理，1964) 设 G 是无环非空简单图，则 1)()()( +Δ≤′≤Δ GGG χ 。 证明：首先， )()( GG Δ≥′χ (定义 6.1.3 的注（4）)。下证 1)()( +Δ≤′ GGχ (用反证法)。 假如 1)()( +Δ>′ GGχ ，令 ),,,( 121 +Δ= EEEc " 是 G 的最佳 1+Δ 边染色。因 1+Δ>′χ ，故 c 必不是正常染色。设 u 是使 )()( uduc < 的顶点。则必存在色 i0，i0 不在 u 处出现（因 1)( ＋Δ 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 。对一般图 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色图⇔ 1G K≅ ； z G 是临界 2色图⇔ 2G K≅ ； z G 是临界 3色图⇔G 是奇圈； 此外，容易证明：（1）任何 k 色图都包含临界 k 色子图；（2）每个色临界图都是连通的 简单图。（留作习题）。 定理 6.2.1 色临界图的顶点割集不是团。 证明（反证法）：假设图 G 是一个临界 k 色图，但有一个点割集 S 是团。记 SG \ 的连 通分支为 nGGG ,,, 21 " 。将 ][SG 按 G 中的连接方式分别与 nGGG ,,, 21 " 相连，得到子图 nGGG ′′′ ,,, 21 " 。 示例:图 G 及点割集 S={u,v} 321 ,, GGG ′′′ 因 G 是 k 色临界的，故每个 iG′是 k－1 色可染的。由于 S 是团，所以 S 中各个顶点在 iG′ 的任何 k－1 染色中必染到相异的色。我们总可以调整各 iG′中颜色的编号，使得 S 中每一个 顶点在各 iG′中染相同的色。这些 iG′的染色合在一起便形成 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，则 2KG ≅ ，故 1)( =′ Gκ 。 下设 3≥k ，用反证法。 假如 1)( −<′ kGκ ，则存在 )(GVS ⊂ 使得 1)(|),(| −<′= kGSS κ 。因 G 是临界 k 色图，故 ][1 SGG = 与 ][2 SGG = 中的顶点都 1−k 色可染。设 ),,,( 1211 −= kUUU "π 和 ),,,( 1212 −= kWWW "π 分别是 1G 和 2G 中点的 1−k 染色。构造二部图 ),( YXH = , },,{ 1,21 −= kxxxX " , },,{ 1,21 −= kyyyY " , 其中 ⇔∈ )(HEyx ji iU 的点与 jW 的点在 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 iji " ，相应地 ijii WUV ∪= ， 则 Vi 是 G 的独立集（ 1,,2,1 −= ki " ），因此 ),,,( 121 −= kVVV "π 是 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 个顶点。证毕。 三、色数的上下界 U1 U2 Uk -1 # S W1 W2 Wk-1 # S x1 x2 xk-1 y2 yk-1 y1 # # 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 个割点（见第二章习题），设 B1、B2 为这样两个块。因 G 本身 2 连通且无割点，故 B1、B2 均有点在 G 中与 z 相邻。设 1Bx∈ 和 2By∈ 是两个与 z 相邻的点。由于 x1 和 x2在不同的块中，因此它们在G { }z− 中不相邻， 因而在 G 中也不相邻，且因 ( ) ( ) 3Gd z Gδ≥ ≥ ，G { , }x y− 连通。 总之，必存在顶点 )(,, GVzyx ∈ ,使得 )(GExy∉ , )(, GEyzxz ∈ 且G { , }x y− 连通。 给 G 的顶点重新编号：首先 yxxx == 21 , ,然后对 },{\ yxGG =′ 中的顶点，按G′中到 z 的距离由远及近的次序依次用 3 4, , ,x x xυ" 编号，即： ),(),( 1 zxdzxd iGiG +′′ ≥ , ( 3, 4, ,i υ= " ),（注意G′仍连通）。 因此 x zυ = ，且对每个 1, 2, , 1i υ= −" , 必存在 ij > 使得 ( )i jx x E G∈ 。由此可知， 对每个 1, 2, , 1i υ= −" ， ix 与 },,,{ 121 −ixxx " 中最多 1)( −Δ G 个顶点相邻（因与 ix 相邻 的至少有一个顶点的下标 i> ），且因 3)()( ≥≥ Gzd δ , 故 1 ( )x x E Gυ υ− ∈ 。 这样一来，可用 )(GΔ 种颜色给顶点进行染色：将 x1和 x2 染色 1，然后按颜色 Δ，，，"21 的顺序依次给 3 4, , ,x x xυ" 进行染色，使相邻两点染不同的色。染法为： 设 11 ,, −ixx " 已染好，考虑 xi , ( 3 1i υ≤ ≤ − )。由于 xi 仅与 11 ,, −ixx " 中最多 1)( −Δ G 个顶点相邻，所以 Δ，，，"21 种颜色中至少有一种颜色α 在 },,,{)( 121 −ii xxxxN "∩ 中未 (x1) x7 x6 x5 x4 x3 (x2) z x9 x y x8x10 9 曾用过，因此可给点 ix 染以颜色α 。因 xυ (=z)既与 x1 又与 x2 相邻，且 x1 和 x2 染的色相同， 所以Δ种色中同样也有一种色 β 在 (N xυ )中未曾用过，（因 ( )d xυ ≤ Δ，而 xυ 的邻点中已 有两点染同一种色，故Δ种色不会全在 ( )N xυ 中出现）。因此可给 xυ 染以色 β 。 如此便得图 G 的一个正常Δ -染色，即有： )()( GG Δ≤χ 。 Case2. G 不是 k 色临界的。此时取 G 的一个临界 k 色子图 H。 (1) 若 H 是完全图，则 H＝ kK ，从而 )(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 ) 1n nΔ + = +1。下面给出的几个上界在 某种程度上是对定理 6.2.3 的改进。 定理 6.2.5 设连通简单图 G 的度序列为 1 2d d dυ≥ ≥ ≥" ，则 (G) 1 max min{ , 1}ii d iχ ≤ + − 证明：将 G 的所有顶点按度的递减（不增）顺序排序，设为 1 2, , ,v v vυ" 。从 v1 开始依次给 顶点染色。在第 i 次染色时，用 vi 的邻点尚未使用的颜色中色号最小的颜色给 vi 染色（事先 对使用的颜色编号），( 1, 2, , )i υ= " 。由于对 vi 染色时，下标比 i 大的顶点尚未染色，而下 标小于 i 的顶点中与 vi 相邻的顶点不超过min{ , 1}id i − 个，因此以使用的颜色数也不会超 过min{ , 1}id i − ，从而按染色规则，对 vi 染色使用的颜色编号不会超过min{ , 1}id i − +1。 时。这个结论对所有 1, 2, ,i υ= " 都成立。因此将 G 的所有顶点全部染色使用的颜色不会 超过max min{ , 1} 1ii d i − + 种。证毕。 定理 6.2.5 对任何图 G， H G (G) 1 max (H)χ δ ⊆ ≤ + 。 证明：对于空图，结论显然成立。因此可设 (G) 2kχ = ≥ 。 取 G 的一个临界 k 色子图 H0，则 0 H G(H ) max (H)δ δ⊆≤ 。由推论 6.1.3， 1 1 3 3 2 2 3 1 1 2 10 0 0 H G (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)k lχ = ≤ + 。证毕。 关于色数的下界有如下定理。 定理 6.2.7 对任何图 G， 2 2(G) 1εχ υ ⎡ ⎤≥ +⎢ ⎥⎢ ⎥ 证明：设 G 的色数是 k，则有 )(GV 的一种划分： ),,,( 21 kVVV "=π ，其中 φ=ji VV ∩ ， )( 1 GVV k i i = = ∪ ，且每个 iV 是非空的独立集 ),,2,1( ki "= 。按分组 1 2, , , kV V V" 的次序将 G 的所有顶点依次编号后，其邻接矩阵可写为如下分块形式 11 12 1 21 22 2 1 2 A(G) k k k k kk A A A A A A A A A ⎛ ⎞⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ " " " " " " " 其中主对角线上每个 iiA 都是零矩阵。 设 | |i iV p= ，则矩阵 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 = ∑ 。利用柯西不等式 2 2 2 1 1 1 ( )( ) ( ) k k k i i i i i i i a b a b = = = ≥∑ ∑ ∑ ，有 k ⋅ 2 1 k i i p = ∑ ≥ 2 2 1 ( ) k i i p υ = =∑ 。从而 2 2υ ε− ≥ 2kυ 。由此解得 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 个非空独立集 1 2, , , kV V V" ，则 (G) | |iVα ≥ ， 1, 2, ,i k= " 。从而 1 ( ) | | k i i k G 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 的 圈 C5。下面我们从 C5 出发递推地由某个不含三角形的 k 色图 Gk构造不含三角形的 k +1 色 图 Gk+1。构造方法如下：设 Gk 的顶点集为{ 1 2, , , nu u u" }，给 Gk 添加 n+1 个新顶点 1 2, , , ,nv v v v" ，每个 vi 与 ui 在 Gk中的所有邻点连边，同时也与 v 连边， 1, 2, ,i n= " 。例 如由 C5 按上述方法构造出的图如下，该图称为 Grötzsch 图。容易检验它是一个无三角形的 4 色图（习题）。下面证明按这种方法构造出的 Gk+1 都是无三角形的 k+1 色图。 令 V*={ 1 2, , , nv v v" }。假如 Gk+1 中有三角形 C3，则 C3 中必含有 V*的点。另一方面， 因 V*是独立集，故 C3 中至多含 V*中的一个点，由于 v 仅与 V*中点有连边，因此不可能出 现在 C3 上。无妨设 C3 的顶点是 , ,i j tu u v 。按 Gk+1 的构造方法，与除 vt 相邻的旧顶点一定与 ut 相邻，这表明 , ,i j tu u u 是 Gk中的一个三角形。这与 Gk中不含三角形矛盾，因此 Gk+1 中不 可能出现三角形。 C5 u1 u3 u2 u3 u5 v1 v2 v3v4 v5 v u1 u3 u2 u3 u5 Grötzsch 图 12 设 (G )k kχ = ，我们来证明 1(G ) 1k kχ + = + 。 首先在 Gk的正常 k 染色基础上，可得到 Gk+1 的正常 k+1 染色。事实上，由于在 Gk+1 中 每个 vi 与相应的 ui 不相邻，因此只要给 vi 染 ui 原有的颜色（ 1, 2, ,i n= " ），而给 v 染第 k+1 种颜色，即可将 Gk 中的正常 k 染色扩充为 Gk+1 中的正常 k+1 染色。由此可知 1(G ) 1k kχ + ≤ + 。 下面来证明 1(G ) 1k kχ + ≥ + ，用反证法。假定 1(G )k kχ + ≤ ，则因 Gk+1 的子图 Gk+1的 色数为 k，因此必有 1(G )k kχ + = 。设π 是 Gk+1 的一个正常 k 染色，通过对颜色重新命名， 总可假定 v 染第 k 种色。由于 v 与所有 vi 相邻，因此 1 2, , , nv v v" 的颜色全在{1, 2, , 1k −" } 中。设在当前染色下，顶点 1 2, , , nu u u" 中染第 k 种颜色的顶点的集合为 Vk。对 i ku V∀ ∈ ， 将其染色改为 ( )ivπ 。我们来证明经过这种改动后，得到 Gk的正常 k−1 染色。 事实上，(1) 由于在原来的染色下 kV 中的顶点染相同的色，因此 kV 中的顶点互不相邻。 (2) V(G )k kV− 中的所有顶点染色未作改变，因此其中相邻的顶点保持不同的色。 (3) 对 i ku V∀ ∈ 和 ( )j k ku V G V∀ ∈ − ，如果它们相邻，则由 Gk+1 的构造知，ui 的相应顶 点 vi 也与 uj相邻，因此在原有染色中 uj 与 vi 染有不同的色，而染色改动后 ui的颜色正是 vi 的颜色，uj 的颜色未变，可见颜色改动后 ui 与 uj 异色。由以上三种情况可知改动后的染色 的确是 Gk的正常 k−1 染色。但这与 Gk是 k 色图矛盾。 至此，我们已证明了 Gk+1 是无三角形的 k+1 色图。证毕。 该定理中由某个不含三角形的 k 色图 Gk构造不含三角形的 k +1 色图 Gk+1的构造方法称 为 Mycielski 构造。 13 §6.3 色多项式 本节要考虑的问题是：对于给定的（标定）图 G，用 k 种颜色（k≥1）对 G 进行正常 顶点染色，共有多少种不同的染色方式？这里两种染色方式不同，是指至少有一个顶点在这 两种染色方式下染有不同的色。 例如，用三种方式给 K3 染色，不同的染色方式有 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 的充分必要条件是 ( )G kχ ≤ ； (2) ( )G 0ε = （即 G 是空图）时， ( , )P G k kυ= ; (3) 若 υ=G K （即 G 是υ阶完全图），则 ( , ) ( 1) ( 1)P G k k k k υ= − − +" 。 证明：（1）P(G, k)>0 当且仅当 G 至少有一种 k 正常染色，即 ( )G kχ ≤ 。 （2）G 是空图则 G 的每个顶点都可以用 k 种颜色中的任一种来染色，故 ( , )P G k kυ= 。 （3）G 是完全图 υK ，则 G 中第一个顶点有 k 种色可选，第二个顶点有 k−1 种色可选，…， 第ν 个顶点有 1k υ− + 种色可选。故 ( , ) ( 1) ( 1)P G k k k k υ= − − +" 。证毕。 设 e 是图 G 的一条边，我们用 G ⋅ e 表示边的收缩，即从 G 中删去 e 并将 e 的两个端点 粘和在一起后所得的图。 定理 6.3.2 设 G 是简单图，对任意 ( )e E G∈ ，有 ( , ) ( , ) ( , )P G k P G e k P G e k= − − ⋅ 。 证明：设 e= uv，考虑用 k 种颜色对 G−e 染色的方式。 （1）对 G−e 染色且使 u 与 v 染同色的方式数恰为 P(G ⋅ e, k)； （2）对 G−e 染色且使 u 与 v 染异色的方式数恰为 P(G, k)。 因此， ( , ) ( , ) ( , )P G k P G e k P G e k= − − ⋅ 。证毕。 利用定理 6.3.2 给出的公式，可以通过减边或增边及边的收缩运算求得一些小阶图的色 多项式。 例 6.3.1 求 1,3K 和 4C 的色多项式。 = 4 3 23 3k k k k− + − . = − ) −(= ( −− ) = − 3 ( ) − ) + 3 ( 1 3 2 v1 v2 v3 3 2 1 v1 v2 v3 2 13 v1 v2 v3 1 23 v1 v2 v3 3 12 v1 v2 v3 2 3 1 v1 v2 v3 14 = ( 1)( 2)( 3) 2 ( 1)( 2) ( 1)k k k k k k k k k− − − + − − + − 2( 1)( 3 3)k k k k= − − + . 定理 6.3.3 设 ( )rh G 表示将 G 的顶点集划分为 r 个非空独立集的划分个数，则 1 ( , ) [ ( ) ( 1)( 2) ( 1)]r r P G k h G k k k k r υ = = − − − +∑ " 。 证明：对每个正整数 r，(1 r k≤ ≤ )，如果 G 不存在正常 r 点染色，则 ( )rh G =0；如果 G 存 在正常 r 点染色（恰使用 r 种颜色），则 G 的顶点集可划分为 r 个非空独立集 1 2, , , rV V V" 。 现用 k 种颜色给这些独立集染色 ( )k r≥ ，使得每个独立集的顶点染一种色，不同独立集的 顶点染不同的色，共有 ( 1)( 2) ( 1)k k k k r− − − +" 中染法。每一种染法都给出 G 的一个正 常 k 点染色。由于将 G 的顶点集划分为 r 个非空独立集的划分有 ( )rh G 种方式，因此对应于 r个独立集划分的各种可能方式共能得到图G的 ( )rh G ⋅ ( 1)( 2) ( 1)k k k k r− − − +" 种正常 k 点染色。当 r 从 1 取至 k 时，得到 1 [ ( ) ( 1)( 2) ( 1)] k r r h G k k k k r = − − − +∑ " 种正常 k 点染色， 这些点染色显然是不同的正常 k 点染色。由于 G 的每种正常 k 点染色都可看作将 G 的顶点 集划分为 k 个独立集（可以有空集），因此都在上述计数之内。这说明 G 的正常 k 点染色的 方式数恰为 1 [ ( ) ( 1)( 2) ( 1)] k r r h G k k k k r = − − − +∑ " ，即 1 ( , ) [ ( ) ( 1)( 2) ( 1)] k r r P G k h G k k k k r = = − − − +∑ " 。 当 k υ< 且 r k> 时， ( 1)( 2) ( 1)k k k k r− − − +" = 0；当 k υ> 且 r υ> 时， ( )rh G = 0。 因此上式与 1 ( , ) [ ( ) ( 1)( 2) ( 1)]r r P G k h G k k k k r υ = = − − − +∑ " 等价。证毕。 我们利用定理 6.3.3 来求 C4 的色多项式。将 C4 划分为两个点独立集只有一种方式，即 相间隔的两点作为一个独立集，因此 2 4( ) 1h C = ；将 C4 划分为三个点独立集有两种方式： 相间隔的两点作为一个独立集，另两点各自作为独立集，因此 3 4( ) 2h C = 。此外，显然 1 4( ) 0h C = ， 4 4( ) 1h C = 。按定理 6.3.3， 2 4( , ) 1 ( 1) 2 ( 1)( 2) 1 ( 1)( 2)( 3) ( 1)( 3 3)P C k k k k k k k k k k k k k k= ⋅ − + ⋅ − − + ⋅ − − − = − − + . 这与前面计算的结果一致。 定理 6.3.4 对任何简单无环图 G，P(G, k)是 k 的整系数υ次多项式，且 （1）首项为 kυ ；（2）第二项为 1kυε −− ；（3）常数项为零；（4）系数正负交替出现。 证明：对ε 作归纳。无妨设 G 是简单图。 0ε = 时， ( , )P G k kυ= ，结论成立。 假设 1mε ≤ − 时结论成立。考虑 mε = 的情形。由归纳假设， = +) + (++ + + 2) == ( 15 2 1 1 ( , ) ( 1) ( 1) i ii i P G e k k k a k υυ υ υε −− − = − = − − + −∑ ， 1 ( , ) ( 1) i ii i P G e k k k b k υυ υ υε −− − − − = ′⋅ = − + −∑31 2 1 ， 其中ε ′是 G⋅e 的边数，ai、bi 是非负整数。由定理 6.3.2， ( , ) ( , ) ( , )P G k P G e k P G e k= − − ⋅ 2 1 1 ( 1) ( 1) i ii i k k a k υυ υ υε −− − = = − − + −∑ 1 [ ( 1) ]i ii i k k b k υυ υ υε −− − − − = ′− − + −∑31 2 1 1 2 2 1 ( ) ( 1) ( )i ii i i k k a k a b k υυ υ υ υ υε ε −− − − − = ′= − + + + − +∑3 。 证毕。 下一个定理是显然的。 定理 6.3.5 （1）若图 G 有 w 个连通分支 G1，G2，…，Gw，则 1 ( , ) ( , ) w i i P G k P G k = = ∏ 。 （2）P(G, k)中系数非零的项的最低次幂为 kw，其中 w 是 G 的连通分支数。 定理 6.3.6 G 是树的充分必要条件是 ( , ) ( 1)P G k k k υ−= − 1 。 证明：充分性。设 ( , ) ( 1)P G k k k υ−= − 1 ，则色多项式的最低次幂是 k 的 1 次项。由定理 6.3.5 知，w=1，即 G 是连通图；又因 ( 1)k k υ−− 1的υ − 1次项的系数是 ( )υ− − 1 ，故ε υ= − 1。 因此 G 是树。 必要性。设 G 是树。下面对 G 的顶点数υ用归纳法来证明 ( , ) ( 1)P G k k k υ−= − 1 。 当υ = 1时，显然 P(G, k) = k，结论成立。 假设对 1nυ ≤ − 的所有树，结论成立。 对 nυ = 的任何树 G，取 G 的一个叶顶点 v0，令G′ = G − v0，则由归纳假设， ( )-1 ( ) 2( , ) ( 1) ( 1)G GP G k k k k kυ υ′ −′ = − = − 。 注意对G′的每一个点正常 k 染色，v0有 k−1 种染色法使 G 正常染色，故 ( )( , ) ( , )( 1) ( 1) GP G k P G k k k k υ −′= − = − 1 。 定理 6.3.7 设 G 是圈，