中科院研究生院专业基础课：《图论与网络流理论》第六章染色理论（高随祥）.pdf

1 第六章染色理论许多实际问题可以归结为求图的匹配或者独立集。此外，在许多应用中，人们希望知道：一个给定的图，它的边集至少能划分成多少个边不交的匹配？或它的顶点集至少能划分成多少个点不交的独立集？这便是图的边染色和顶点染色问题。 §6.1 边染色定义 6.1.1 非空无环图 G 的边正常 k 染色（proper edge k- colouring）是指 k 种颜色12 , ，，" k 对 E(G)中元素的一种分配，使得相邻两条边所染颜色不同。换句话说，G 中边正常 k 染色是映射 c : E(G) → {1,2,", k}，使得对每个 i (i = 1,2,", k ), ( ) 1 c i − 是匹配或者空集。注：若令 ( ) { ( ) ( ) }, ( 1,2, , ) 1 E c i e E G c e i i k i = − = ∈ = = " ，则 G 的一个边正常 k 染色可看成是边集的一种划分 ( , , , ) E1 E2 Ek c = " ，其中每个 Ei是匹配或空集。例如，下面给出了 5-圈的一种边正常 3 染色和 Petersen 图的一种边正常 4 染色。定义 6.1.2 若存在 G 的一种边正常 k 染色，则称 G 是边 k 色可染的（edge k-colourable）。注：（1）每个无环非空图的边必ε 色可染。（2）若 G 是边 k 色可染的，则对∀l ≥ k , G 也是 l 色可染的。定义 6.1.3 正整数 χ′(G) = min{k G 是边 k 色可染的}称为 G 的边色数 (edge chromatic number)。注：（1）若 χ′(G)＝k ，则 G 中边的任何 k 染色 ( , , , ) E1 E2 Ek c = " 中每个 Ei 都是非空的匹配。（2）G 的边色数 χ′(G)是 G 中边不交匹配的最小数目。（3） ( ) 2 1 ( ) K2n = n − = Δ K2n χ′ （因完全图 K2n有 2n-1 个边不交的匹配）（4）χ′(G) ≥ Δ(G) 。（设d(v) = Δ(G) ，则与 v 关联的 Δ(G) 条边至少需 Δ(G) 种色才能正常染色）。引理 6.1.1. 设 G 是非空无环的连通图，且不是奇圈，则存在 G 的边 2-染色，使得所用的两种色在每个度≥ 2的顶点处都出现。证明：（1）设 G 是 Euler 图，则 G 中无奇度点。若 G 本身是一个偶长度圈，则命题显然。若 G 不是一个偶长度圈，则 G 至少有一个顶点 v0满足d(v0 ) ≥ 4 (否则，G 中所有顶点都是 2 度的，由于 G 连通，从而 G 是圈，由引理条件，G 不是奇圈，故为偶圈，矛盾)。 3 3 4 1 1 3 2 2 1 3 1 2 4 2 2 3 2 1 1 2

设neve2…ev是G的一条Eer闭迹。令E1={e1为奇数},E2={ei为偶数}。于是c=(E1,E2)即为所求的边2-染色需要说明的是,Euer闭迹从度≥4的顶点出发是必需的。例如在下图中,若从2度顶点α处出发沿 Euler闭迹交替地对边进行2染色,则u点可能仅能获得一种色(如图,1、2 表示两种颜色)。 (2)设G不是 Euler图。此时给G增添一个新顶点v,将v与G的每个奇度顶点连一条边,得到一个新图G。显然G的所有顶点都是偶数度的,因而是 Euler图。设 ee2…eGny0是G的一个Euer闭迹,令E1={e|i为奇数},E2={ei为偶数},这样可得G的一个边2-染色c=(E1,E2),(其中v点的关联边有可能是同一种色)。按这种办法给G的边染色后,去掉vo及其关联的边,便得到G的一个边2-染色。对于G中偶度点,它关联的边及其颜色与G中相同:对G的任何奇度点v,在G中比在G中少关联条边,但只要dG(v)>1,便有d(v)≥3,故由染色的方法知,与v点关联的边中两种颜色的都有。这说明G的边2染色c=(E∩E(G),E2∩E(G)即为所求的边2-染色。证毕。定义614对于G的一个边k染色c,c(v)表示顶点v处出现的不同颜色的数目。设c与c 都是G的边k-染色(未必是正常染色)。若相应的c(v)与c(v)满足: ∑c(v)>∑c(v) 则称c'是对c的一个改进。不能改进的边k染色称为最佳边k染色。引理612设C=(E1,E2,…,E)是G的一个最佳边k染色,且存在一个顶点a及两种颜色 i和j色不在u处出现,而色j在u处出现了至少两次,则GEUE,]中含u的连通分支必是奇圈。证明:设G1是GE,UE中含的连通分支。若G1不是奇圈,则由引理61,G1有一个边-2染色,其两种色在G1中度≥2的每个顶点处都出现。按这种染色办法用色i和j给 EUE中的边重新染色后,得到G的一个新的边k染色c=(E1,E2,…E),其中,j 两色都在u处出现,故c()=c()+1,而对u之外的其它顶点v,都有c(v)≥c(v)。于是 ∑c()>∑c(v)。这与c是最佳边k染色矛盾。证毕 vEP( 定理61( Konig,1916)设G是二部图,则z'(G)=△(G)。 1]D. Konig, Uber Graphen und ihre Anwendung auf Determinantentheorie und mengenlehre Math.Ann,77(1916),453-465 证明(反证法):假设x'(G)≠△(G)。则由定义613的注(4),x(G)>△(G)。设 C=(E1,E2,…,EA)是G的一个最佳边△染色,则c必定不是正常染色。故存在顶点u满足c()<d(),因而必有某两条在u点相邻的边染了同一种色。而且,因d()≤△(G),故

2 设 0 1 1 2 0 v e v e e v " ε 是 G 的一条 Euler 闭迹。令 E e i i { 1 = 为奇数}，E e i 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 1 1 2 ( *) 0 v e v e e v " ε G 是 G* 的一个 Euler 闭迹，令 E e i i { * 1 = 为奇数}, E e i i { * 2 = 为偶数}，这样可得 G* 的一个边 2-染色 ( , ) * 2 * 1 * c = E E ，（其中 0 v 点的关联边有可能是同一种色）。按这种办法给 G* 的边染色后，去掉 0 v 及其关联的边，便得到 G 的一个边 2-染色。对于 G 中偶度点，它关联的边及其颜色与 G* 中相同；对 G 的任何奇度点 v，在 G 中比在 G* 中少关联一条边，但只要dG (v) > 1 , 便有dG (v) ≥ 3 , 故由染色的方法知，与 v 点关联的边中两种颜色的都有。这说明 G 的边 2-染色 ( ( ), ( )) * 2 * c = E1 ∩ E G E ∩ E G 即为所求的边 2-染色。证毕。定义 6.1.4 对于 G 的一个边 k-染色 c，c(v)表示顶点 v 处出现的不同颜色的数目。设 c 与c′ 都是 G 的边 k-染色（未必是正常染色）。若相应的 c(v)与c′(v)满足： ∑ ∑ ∈ ∈ ′ > ( ) ( ) ( ) ( ) v V G v V G c v c v , 则称c′是对 c 的一个改进。不能改进的边 k 染色称为最佳边 k 染色。引理 6.1.2 设 ( , , , ) E1 E2 Ek c = " 是 G 的一个最佳边 k 染色，且存在一个顶点 u 及两种颜色 i 和 j, 色 i 不在 u 处出现，而色 j 在 u 处出现了至少两次，则 [ ] G Ei ∪ Ej 中含 u 的连通分支必是奇圈。证明：设 G1是 [ ] G Ei ∪ Ej 中含 u 的连通分支。若 G1 不是奇圈，则由引理 6.1.1，G1有一个边-2 染色，其两种色在 G1 中度≥ 2的每个顶点处都出现。按这种染色办法用色 i 和 j 给 Ei ∪ Ej 中的边重新染色后，得到 G 的一个新的边 k-染色 ( , , , ) E1 E2 Ek c′ = ′ ′ " ′ ，其中 i, j 两色都在 u 处出现，故c′(u) = c(u) +1,而对 u 之外的其它顶点 v，都有c′(v) ≥ c(v) 。于是 ∑ ∑ ∈ ∈ ′ > ( ) ( ) ( ) ( ) v V G v V G c v c v 。这与 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 > Δ 。设 ( , , , ) = E1 E2 EΔ c " 是 G 的一个最佳边 Δ 染色，则 c 必定不是正常染色。故存在顶点 u 满足c(u) < d(u) ，因而必有某两条在 u 点相邻的边染了同一种色。而且，因du 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 是无环非空简单图，则 Δ(G) ≤ χ′(G) ≤ Δ(G) +1。证明：首先， χ′(G) ≥ Δ(G) (定义 6.1.3 的注（4）)。下证 χ′(G) ≤ Δ(G) +1(用反证法)。假如 χ′(G) > Δ(G) +1 ，令 ( , , , ) = E1 E2 EΔ+1 c " 是 G 的最佳 Δ +1 边染色。因 χ′ > Δ +1，故 c 必不是正常染色。设 u 是使c(u) < d(u) 的顶点。则必存在色 i0，i0 不在 u 处出现（因d(u) < Δ＋1），同时也存在色 i1，i1 至少在 u 处出现两次。设 uv 和 uv1 染有颜色 i1（如图）。因 ( ) 1 d v1 < Δ + ，故必有某种色 2 i 不在 v1 处出现。这样 2 i 必然在 u 处出现（否则，可用 2 i 给 uv1 重新染色，得到一个改进的 Δ＋1边染色，与 c 是最佳染色矛盾）。因此存在一条边 uv2 染有色 2 i 。又因 ( ) 1 d v2 < Δ + ，必有某种色 3i 不在 v2 处出现。 3i 必然在 u 处出现（理由同上）。因此存在一边 uv3 染有色 3i 。继续这个过程，可找出一个顶点序列v1, v2 ,", 以及一个颜色序列i 1,i2 ,", 使得边 uvj 染有颜色 ij，且色 ij+1 不在点 vj 处出现，（ j = 1,2,"）。而且，因c(u) < d(u) 且 d(u) 是有限数，故存在一个最小整数 m，使得对某个 k < m，有 im+1 = ik。现在，对1 ≤ j ≤ k −1, 用颜色 ij+1 给边 uvj 重新染色。这样产生一个新的( Δ＋1)边染色 ( , , , ) 1 2 Δ+1 C′ = E′ E′ " E′ 。显然对所有 v ∈V , c′(v) ≥ c(v) 。因此 c′ 也是 G 的一个最佳 (Δ +1) 边染色。由引理 6.1.2， [ ] 0 k G Ei Ei ′ ∪ ′ 中含有 u 的那个分支 H1 是个奇圈。 … u v v3 v2 v1 vk vk-1 vm i1 i1 i2 im ik-1 ik i3 … … … u v v3 v2 v1 vk vk-1 vm i1 i2 i3 im ikik i4 … … i0 i0 ik ik H1

而对k≤j≤m-1,用颜色+给w重新染色,而用颜色给mm重新染色,得到个(△+1)边染色c"=(E1,E2,…,EA1)。同理有c"(v)≥c(v)对所有v∈V成立。故由引理 612,GE"UE"]中含有n的分支H2是个奇圈但是,因v在H1中的度为2(恰与一条色边和一条色边相关联),故它在H2中的度为1(仅与一条i色边相关联)。这与H2是奇圈矛盾。(注意vk必在分支H2中,因它与 vk-1有o、交错路(H1的段)相连)。由此可知反证法假设不能成立。证毕对于有重边的图G,设(G)表示G中边的最大重数, Vizing实际上证明了一个更一般的结论:△(G)≤x(G)≤△(G)+(G) vizing定理提出了一个分类问题:使x'(G)=△(G)的简单图称为第一类图,使 x'(G)=Δ(G)+1的简单图G称为第二类图。确定一个图属于第一类还是第二类是很困难的,目前仅对少量的图类判明了它们所属的类。路、树、二部图、偶数阶完全图、轮图都是第一类图(轮图Wn是由一个点与长为n的圈上所有顶点相连形成的图),奇圈、奇数阶完全图都是第二类图(见有关定理和习题)。一般情况下判别一个图属于第几类图,尚没有好的充分必要判别条件,一些充分性判别条件见习题。第二类图相对较稀少。在υ≤6的143个连通简单图中仅有8个属于第二类;而Erd6s 和Wom(1970证明:im|c(y)=1,其中c()表示D阶第i类图的集合。这 →=|c1(v)Uc2(v) 表明当顶点数充分大时,几乎所有非空简单图都是第一类图已经知道存在最大度为2,3,4,5的第二类平面图,但 Vizing(1965)已证明:不存在最大度≥8的第二类平面图。目前尚不知道是否存在最大度为6或7的第二类平面图由 vizing定理,每个无环非空简单图G都是可(△+1)边可染色的。实际上,可以根据引理6.1.1和引理6.1.2给出求图G的正常(△+1)边染色的多项式时间算法。但是,求一般图G的边色数z(G)及其相应的正常边染色尚无多项式时间算法。事实上,已经证明这是一个NPC问题1。求二部图的边色数的一个多项式时间算法将在§64中介绍。有关边染色的更多内容可参看[3]。 2]1. 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

4 而对k ≤ j ≤ m −1，用颜色 ij+1 给 uvj重新染色，而用颜色 ik给 uvm重新染色，得到一个( Δ＋1)边染色 ( , , , ) 1 2 Δ+1 c′′ = E′′ E′′ " E′′ 。同理有c′′(v) ≥ c(v) 对所有v ∈V 成立。故由引理 6.1.2， [ ] 0 k G Ei Ei ′′ ∪ ′′ 中含有 u 的分支 H2 是个奇圈。但是，因 vk在 H1 中的度为 2（恰与一条 i0 色边和一条 ik色边相关联），故它在 H2 中的度为 1（仅与一条 i0 色边相关联）。这与 H2 是奇圈矛盾。（注意 vk必在分支 H2 中，因它与 vk－1有 i0、ik交错路（ H1 的一段）相连）。由此可知反证法假设不能成立。证毕。对于有重边的图 G，设 μ(G)表示 G 中边的最大重数，Vizing 实际上证明了一个更一般的结论： Δ(G) ≤ χ′(G) ≤ Δ(G) + μ(G) 。 Vizing 定理提出了一个分类问题：使 χ′(G) = Δ(G) 的简单图称为第一类图，使 χ′(G) = Δ(G) +1的简单图 G 称为第二类图。确定一个图属于第一类还是第二类是很困难的，目前仅对少量的图类判明了它们所属的类。路、树、二部图、偶数阶完全图、轮图都是第一类图（轮图W1,n 是由一个点与长为 n 的圈上所有顶点相连形成的图），奇圈、奇数阶完全图都是第二类图(见有关定理和习题)。一般情况下判别一个图属于第几类图，尚没有好的充分必要判别条件，一些充分性判别条件见习题。第二类图相对较稀少。在υ ≤ 6 的 143 个连通简单图中仅有 8 个属于第二类；而 Erdös 和 Wilson(1977)已证明： 1 | ( ) ( ) | | ( ) | lim 1 2 1 = →∞ ν ν ν c c 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 v3 v2 v1 vk vk-1 vm i1 i2 i3 im ikik＋1 i4 … … i0 i0 ik ik H2 ik

中科院研究生院专业基础课：《图论与网络流理论》第六章 染色理论（高随祥）

中科院研究生院专业基础课：《图论与网络流理论》第六章染色理论（高随祥）