1 第六章 染色理论 许多实际问题可以归结为求图的匹配或者独立集。 此外， 在许多应用中， 人们希望知道： 一个给定的图， 它的边集至少能划分成多少个边不交的匹配？或它的顶点集至少能划分成多 少个点不交的独立集？这便是图的边染色和顶点染色问题。 § 6.1 点染色 定义 6.1.1 设 G 是一个无环边的图。 G 的顶点 正常 k 染色 (proper vertex k-colouring)π 是指 k 种颜色 k，，， L21 对于 G 的各顶点的一种分配，使得任二相邻的顶点被染上不同的颜色。换 句话说， G 的顶点正常 k 染色 π 是一个映射 },,2,1{)(: kGV L→π , 使得 )( 1 i ? π 是独立集或空集 ),,2,1( ki L= . 注 ：设 π 是 G 的一个顶点正常 k 染色。令 })(|)({)(V 1 ixGVxi i =∈== ? ππ ， （ ki ,,2,1 L= ） 。 则 π 实际上是对顶点集 )(GV 的一种划分： ),,,( 21 k VVV L=π ，其中 φ= ji VV I ， )( 1 GVV k i i = = U ，且每个 i V 是独立集或空集 ),,2,1( ki L= . 例 ： 定义 6.1.2 若存在 G 的一种顶点正常 k 染色， 则称图 G 是 点 k 色可染的 (vertex k-colourable)， 有时简称为 k 色可染的 或 可 k 染色的 。 注 ：⑴ 每个图 G 一定是 )(Gν 色可染的。 ⑵ 若图 G 是 k 色可染的，则对任何正整数 km ≥ ， G 也 m 色可染。 定义 6.1.3 设 G 是无环边的图，令 GkG |min{)( =χ 是 k 色可染的 }， 称 )(Gχ 为 G 的 点色数 ，有时简称为 色数 (chromatic number)。若 kG =)(χ ，则称 G 为 k 色 图 (k-chromatic graph)。 3 1 3 2 2 1 3 1 1 2 2 注 ： （ 1） 若 kG =)(χ （即 G 是 k 色图） ，则 G 中任何点 k 染色 ),,,( 21 k VVV L=π 中每个 i V 都 是非空的独立集。换言之， G 的色数是 G 中点不交的独立集的最小数目。 （2）易证： null 1)( =Gχ ? ν KG = ； null 2)( =Gχ ?G 是非空二部图； null )()( GG νχ = ? ν KG ? 。 （3） 3)( 12 = +n Cχ 。 （4） 3)( ≥Gχ ? G 含有奇圈。 （5）四色定理：对任何平面图 G， 4)( ≤Gχ 。 点染色理论的基本问题 ：给定图 G，确定 )(Gχ 的值。 研究现状 ：对一般情况，给出了 )(Gχ 的范围（用 G 的参数表示） ；对某些特殊图类，确定 出了 )(Gχ 的确切值。 定义 6.1.4 设 )1(,)( ≥= kkGχ 。若对 G 的任何真子图 H，均有 kH <)(χ ，则称 G 是 临界 k 色图 （ critical k-chromatic graph）. 注： （1） G 是临界 1 色图 ? 1 G K? ； G 是临界 2 色图 ? 2 G K? ； G 是临界 3 色图 ?G 是奇圈； （2） Grótzsch 图是临界 4 色图； Grótzsch图 （3）任何 k 色图都包含一个临界 k 色子图； （4）每个色临界图都是连通的。 定理 6.1.1 色临界图的顶点割集不是团。 证明（反证法） ：假设图 G 是一个临界 k 色图，但有一个点割集 S 是团。记 SG \ 的连 通分支为 n GGG ,,, 21 L 。将 ][SG 按 G 中的连接方式分别与 n GGG ,,, 21 L 相连，得到子图 n GGG ′′′ ,,, 21 L 。 3 示例:图 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.1.1 每个色临界图都是块（即不含割点，亦即 2 连通） 。 证明：假如某临界图不是块，则它有割点。这个割点构成一个团，与定理 6.1.1 矛盾。证毕。 下一个推论是显然的。 推论 6.1.2 若临界 k 色图 G 有 2 顶点割集 },{ vu ，则 u 与 v 不相邻。 定理 6.1.2 (Dirac,1952) 设 G 是临界 k 色图（ k≥2） ，则边连通度 kG ≥′ )(κ 。 证明：若 k = 2，则 2 KG ? ，故 1)( =′ GK 。 下设 3≥k ，用反证法。 假如 1)( ?<′ kGκ ，则存在 )(GVS ? 使得 1)(|),(| ?<′= kGSS κ 。因 G 是临界 k 色图，故 ][ 1 SGG = 与 ][ 2 SGG = 中的顶点都 1?k 色可染。设 ),,,( 1211 ? = k uuu Lπ 和 ),,,( 1212 ? = k www Lπ 分别是 1 G 和 2 G 中点的 1?k 染色。构造二部图 ),( YXH = , },,{ 1,21 ? = k xxxX L , },,{ 1,21 ? = k yyyY L , 其中 ?∈ )(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 u v u v u v u v y 1 U 1 U 2 U k -1 M S W 1 W 2 W k-1 M S x 1 x 2 x k-1 y 2 y k-1 y 1 M M H 4 的每个顶点至多能覆盖 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 L ，相应地 i jii WUV U= ， 则 V i 是 G 的独立集（ 1,,2,1 ?= ki L ） ，因此 ),,,( 121 ? = k VVV Lπ 是 G 的一个点 k-1 染色。 但这与 kG =)(χ 矛盾，故 1)( ?≥′ kGκ 。证毕。 推论 6.1.3 设 G 是临界 k-色图，则 1)( ?≥ kGδ 。 证明：由定理 )()()( GGG κκδ ≥′≥ 及定理 6.1.2，有 1)()( ?≥′≥ kGG κδ 。证毕。 推论 6.1.4 任何 k 色图至少有 k 个顶点的度 1?≥ k 。 证明：设 G 是 k 色图， H 是其一个临界 k 色子图，由推论 6.1.3， H 的每个顶点在 H 中的度 1?≥ k ，故在 G 中的度也 1?≥ k ，由于 H 是 k 色临界的，因此它至少有 k 个顶点。证毕。 推论 6.1.5 对任何简单图 G， 1)()( +?≤ GGχ 。 证明：设 kG =)(χ ,且 H 是 G 的临界 k 色子图，由推论 6.1.3， 1)( ?≥ kGδ 。故 1)(1)()()( ?=?≥≥?≥? GkHHG χδ 。证毕。 引理 设 G 是具有 2 顶点割 {u,v}的 k 色临界图，则 53)()( ?≥+ kvdud 。 该引理的证明见 Bondy & Murty 著《图论及其应用》第 8 章。 定理 6.1.3 (Brooks， 1941) 设 G 是连通的简单图，且 G 既不是奇圈又不是完全图，则 )()( GG ?≤χ 。 证明：设 G 是满足定理条件的 k 色图。如果 G 不是 k 色临界的，则取其一个 k 色临界子图 H。若 H 是完全图，则 H＝ k K ，从而 )(1)(1)1()()( GHkkHG ?≤+?=+?=== χχ （ G 中至少有一条不属于 H 的边） ； 若 H 是一个奇圈，则 )(3)()( GHG ?≤== χχ （ G 中至少有一条不属于 H 的边） 。 因此，可以假定 G 是 k 色临界的。由推论 6.1.1， G 是一个块。又由于色 1 临界图和色 2 临界图是完全图，而色 3 临界图是奇圈，故 4≥k 。 如果 G 有 2 顶点割 {u,v}，则由引理， 1253)()(2 ?≥?≥+≥? kkvdud 。注意此式左右 两端分别是偶数和奇数，故 k22 ≥? ，从而结论成立。以下假定 G 是 3 连通的。 由于 G 不是完全图， 因此必存在顶点 )(,, GVzyx ∈ ,使得 )(GExy? ,而 )(, GEyzxz ∈ . 给 G 的顶点重新编号：首先 yxxx == 21 , ,然后对 },{\ yxGG =′ 中的顶点，按 G′中到 z 5 的距离由远及近的次序依次用 ν xxx ,,, 43 L 编号，即： ),(),( 1 zxdzxd iGiG +′′ ≥ , ( ν,,4,3 L=i ),（注意 G′仍连通） 。 因此 zx = ν ， 且对每个 1,,2,1 ?= νLi , 必存在 ij > 使 得 )(HExx ji ∈ 。 由此可知， 对每个 1,,2,1 ?= νLi ， i x 与 },,,{ 121 ?i xxx L 中最多 1)( ?? G 个顶点相邻（因与 i x 相邻的至少有一个顶点的下标 i> ） ，且因 3)()( ≥≥ Gzd δ , 故 )( 1 GExx ∈ ? νν 。 这样一来， 可用 )(G? 种颜色给顶点进行染色： 将 x 1 和 x 2 染色 1， 然后按颜色 ?，，， L21 的顺序依次给 ν xxx ,,, 43 L 进行染色，使相邻两点染不同的色。染法为： 设 11 ,, ?i xx L 已染好，考虑 x i , ( 13 ?≤≤ νi )。由于 x i 仅与 11 ,, ?i xx L 中最多 1)( ?? G 个顶点相邻，所以 ?，，， L21 种颜色中至少有一种颜色 α 在 },,,{)( 121 ?ii xxxxN LI 中未 曾用过，因此可给点 i x 染以颜色 α 。因 ν x (=z)既与 x 1 又与 x 2 相邻，且 x 1 和 x 2 染的色相同， 所以 ? 种色中同样也有一种色 β 在 ν xN( )中未曾用过， （因 ?≤)( ν xd ，而 ν x 的邻点中已 有两点染同一种色，故 ? 种色不会全在 )( ν xN 中出现） 。因此可给 ν x 染以色 β 。 如此便得图 G 的一个正常 ? -染色，即有： )()( GG ?≤χ 。证毕。 例 ：求 Peterson 图的色数。 解：因 Peterson 图 G 含有奇圈，故不是二部图，因而 3)( ≥Gχ ； 另一方面， G既不是奇圈又不是完全图，且 3)( =? G , 故 3)()( =?≤ GGχ 。因此， 3)( =Gχ 。 习 题 九 1. 证明：若 G 的任二奇圈都有一个公共顶点，则 5)( ≤Gχ 。 2. 证明： )(max1)( HG GH δχ ? +≤ 。 3. 证明： （1） 1)( =Gχ ? ν KG = ； （2） 2)( =Gχ ?G 是非空二部图； （3） )()( GG νχ = ? ν KG ? 。 （4） 3)( 12 = +n Cχ 。 3 1 3 2 2 1 3 1 1 2 (x 1 ) x 7 x 6 x 5 x 4 x 3 (x 2 ) z x 10 x 9 x y x 8 6 （5） 3)( ≥Gχ ? G 含有奇圈。 5. 证明： （1） G 是临界 1 色图 ? 1 G K? ； （2） G 是临界 2 色图 ? 2 G K? ； （3） G 是临界 3 色图 ?G 是奇圈； （4） 任何 k 色图都包含一个临界 k 色子图； （5） 每个色临界图都是连通的。 7 § 6.2 边染色 定义 6.2.1 非空无环图 G 的边正常 k 染色 （ proper edge k- colouring） 是指 k 种颜色 k，，， L21 对 E(G)中元素的一种分配，使得相邻两条边所染颜色不同。换句话说， G 中边的 k 染色是 映射 },,2,1{)(: kGEc L→ ， 使得对每个 i ( ki ,,2,1 L= ), )( 1 ic ? 是匹配或者空集。 注 ：若 令 ),,2,1(},)()({)( 1 kiiecGEeicE i L==∈== ? ，则 G 的一个边 k 染色可看成是 边集的一种划分 ),,,( 21 k EEEc L= ，其中每个 E i 是匹配或空集。 例 ： 定义 6.2.2 若存在 G 的一种边正常 k 染色，则称 G 是 边 k 色可染的 （ edge k-colourable） 。 注 ： （ 1）每个无环非空图的边必 ε 色可染。 （ 2）若 G 是边 k 色可染的，则对 kl ≥? , G 也是 l 色可染的。 定义 6.2.3 正整数 GkG min{)( =′χ 是边 k 色可染的 }称为 G 的边色数 (edge chromatic number)。 注 ： （ 1）若 kG ＝)(χ′ ，则 G 中边的任何 k 染色 ),,,( 21 k EEEc L= 中每个 E i 都是非空的 匹配。 （ 2） G 的边色数 )(Gχ′ 是 G 中边不交匹配的最小数目。 （ 3） )(12)( 22 nn KnK ?=?=′χ （因完全图 K 2n 有 2n-1 个边不交的匹配） （ 4） )()( GG ?≥′χ 。 （设 )()( Gvd ?= ，则与 v 关联的 )(G? 条边至少需 )(G? 种色才 能正常染色） 。 引理 6.2.1. 设 G 是非空无环的连通图，且不是奇圈，则存在 G 的边 2-染色，使得所用的两 种色在每个度 2≥ 的顶点处都出现。 证明 ： （ 1）设 G 是 Euler 图，则 G 中无奇度点。 若 G 本身是一个偶长度圈， 则命题显然。 否则， G 至少有一个顶点 v 0 满足 4)( 0 ≥vd (不 然的话， G 中所有顶点都是 2 度的，又由于 G 连通，从而 G 是圈，由条件， G 不是奇圈， 故为偶圈 )。 设 02110 veevev ε L 是 G 的一条 Euler 环游。 令 ieE i { 1 = 为奇数 }， ieE i { 2 = 为偶数 }。 于是 c = (E 1 , E 2 ) 即为所求的边 2-染色。 3 3 1 2 1 2 3 1 2 2 1 3 2 4 2 1 4 1 2 3 3 8 注 ：为何要从度 4≥ 的顶点出发？例： 若从 u 点出发，则 u 点可能获得一种色。 (2) 设 G 不是 Euler 图。此时给 G 增添一个新顶点 v 0 ，将 v 0 与 G 的每个奇度顶点连一条 边，得到一个新图 G * 。显然 G * 的所有顶点都是偶数度的，因而是 Euler 图。设 0*)(2110 veevev Gε L 是 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 II= 即为所求的边 2-染色。证毕。 定义 6.2.4 对于 G 的一个边 k-染色 c， c(v)表示顶点 v 处出现的不同颜色的数目。 设 c 与 c′ 都是 G 的边 k-染色（未必是正常染色） 。若相应的 c(v)与 )(vc′ 满足： ∑∑ ∈∈ >′ )()( )()( GVvGVv vcvc , 则称 c′是对 c 的一个 改进 。不能改进的边 k 染色称为 最佳边 k 染色 。 引理 6.2.2 设 ),,,( 21 k EEEc L= 是 G 的一个最佳边 k 染色， 且存在一个顶点 u 及两种颜色 i 和 j, 色 i 不在 u 处出现，而色 j 在 u 处出现了至少两次，则 ][ ji EEG U 中含 u 的连通分支 必是奇圈。 证明： 设 G 1 是 ][ ji EEG U 中含 u 的连通分支。若 G 1 不是奇圈，则由引理 6.2.1， G 1 有一个 边-2 染色，其两种色在 G 1 中度 2≥ 的每个顶点处都出现。按这种染色办法用色 i 和 j 给 ji EE U 中的边重新染色后，得到 G 的一个新的边 k-染色 ),,,( 21 k EEEc ′′′=′ L ，其中 i, j 两色都在 u 处出现，故 1)()( +=′ ucuc ,而对 u 之外的其它顶点 v，都有 )()( vcvc ≥′ 。于是 ∑∑ ∈∈ >′ )()( )()( GVvGVv vcvc 。这与 c 是最佳边 k-染色矛盾。证毕。 定理 6.2.1 设 G 是二部图，则 )() GG ?=′（χ 。 证明 1（反证法） 。假设 )() GG ?≠′（χ 。则由定义 6.2.3 的注（ 4） ， )() GG ?>′（χ 。设 ),,,( 21 ? = EEEc L 是 G 的一个最佳边 ? 染色，则 c 必定不是正常染色。故存在顶点 u 满 足 )()( uduc < (因 G 不是正常染色，必有某两条相邻的边染了同一种色 )。而且，因 )()( Gud ?< , 故 ? 种色中必有某种色不在 u 上出现。显然 u 满足引理 6.2.2 的条件，因此 G 中有奇圈。这与 G 是二部图矛盾。证毕。 u 1 2 1 2 1 1 2 9 证明 2. 因二部图有 )(G? 个边不交的匹配，故 )() GG ?=′（χ 。证毕。 定理 6.2.4 (Vizing 定理， 1964)。设 G 是无环非空简单图，则 1)()()( +?≤′≤? GGG χ 。 证明： 首先， )()( GG ?≥′χ (定义 6.2.3 的注（ 4） )。下证 1)()( +?≤′ GGχ ， (用反证法 )。 假如 1)()( +?>′ GGχ ，令 ),,,( 121 +? = EEEc L 是 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 。 继续这个过程，就找出一个顶点序列 L,, 21 vv , 以及一个颜色序列 L,, 21 ii , 使得边 uv j 染有颜色 i j ，且色 i j+1 不在点 v j 处出现， （ L,2,1=j ） 。而且，因 )()( uduc < 且 )(ud 是有 限数，故存在一个最小整数 m，使得对某个 k < m，有 i m+1 = i k 。 现在，对 11 ?≤≤ kj , 用颜色 i j+1 给边 uv j 重新染色。这样产生一个新的 ( 1＋? )边染色 ),,,( 121 +? ′′′=′ EEEC L 。显然对所有 Vv∈ , )()( vcvc ≥′ 。因此 c′也是 G 的一个最佳 )1( +? 边染色。由引理 6.2.2， ][ 0 k ii EEG ′′ U 中含有 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 10 而对 1?≤≤ mjk ，用颜色 i j+1 给 uv j 重新染色，而用颜色 i k 给 uv m 重新染色，得到一 个 ( 1＋? )边染色 ),,,( 121 +? ′′′′′′=′′ EEEc L 。同理有 )()( vcvc ≥′′ 对所有 Vv∈ 成立。故由引理 6.2.2， ][ 0 k ii EEG ′′′′ U 中含有 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 的一段）相连） 。由此可知反证法假设不能成立。证毕。 注 ： 1. 对于有重边的图 G，设 )(Gμ 表示 G 中边的最大重数， Vizing 实际上证明了一个更 一般的结论： )()()()( GGGG μχ +?≤′≤? 。 2. Vizing 定理提出了一个分类问题：使 )()( GG ?=′χ 的简单图称为第一类图，使 1)()( +?=′ GGχ 的简单图 G 称为第二类图。 （ 1） 二部图和 K 2n 都是第一类图；而 C 2n+1 和 K 2n+1 是第二类图。 （ 2） 一般情况下，什么样的图属于第一类图，什么样的图属于第二类图的问题尚未 解决。 （ 3） 第二类图较稀少： 在 6≤ν 的 143 个连通简单图中仅有 8 个属于第二类； 而 Erd?s 等已证明： 1 |)()(| |)(| lim 21 1 = ∞→ νν ν cc c v U , 其中 )(ν i c 表示 ν 阶第 i类图的集合。 这表明几乎所有非空简单图都是第一类图。 （ 4） 已经知道存在最大度为 2， 3， 4， 5 的第二类平面图，但 Vizing (1965)已证明： 不存在最大度 8≥ 的第二类平面图。目前尚不知道是否存在最大度为 6 或 7 的 第二类平面图。 3. 由 Vizing 定理，每个无环非空简单图 G 都是可（ 1+? ）边可染色的。实际上，可以根 据引理 6.2.1 和引理 6.2.2 给出求图 G 的正常（ 1+? ）边染色的多项式时间算法。但是，求 一般图 G 的边色数 )(Gχ′ 及其相应的正常边染色尚无多项式时间算法。事实上，已经证明， 这是一个 NPC 问题 ]4[ 。 … 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