第六章染色理论 许多实际问题可以归结为求图的匹配或者独立集。此外,在许多应用中,人们希望知道: 一个给定的图,它的边集至少能划分成多少个边不交的匹配?或它的顶点集至少能划分成多 少个点不交的独立集?这便是图的边染色和顶点染色问题。 §6.1边染色 定义6.11非空无环图G的边正常k染色( proper edge k-colouring)是指k种颜色1,2,…,k 对E(O)中元素的一种分配,使得相邻两条边所染颜色不同。换句话说,G中边正常k染色 是映射 c:E(G)→>{1,2,…k} 使得对每个i(i=1,2,…,k),c(1)是匹配或者空集 注:若令E,=C()={e∈E(G)k(e)=l},(=1.2,…,k),则G的一个边正常k染色可看 成是边集的一种划分C=(E1,E2,…,E6),其中每个E是匹配或空集。 例如,下面给出了5-圈的一种边正常3染色和 Petersen图的一种边正常4染色。 定义6.1.2若存在G的一种边正常k染色,则称G是边k色可染的( edge k-colourable) 注:(1)每个无环非空图的边必E色可染。 (2)若G是边k色可染的,则对V≥k,G也是l色可染的 定义6.3正整数x(G)=minG是边k色可染的}称为G的边色数( (edge chromatic numbe 注:(1)若x(G=k,则G中边的任何k染色C=(E1,E2,…,E)中每个E都是非空的 匹配。 (2)G的边色数z(G)是G中边不交匹配的最小数目 (3)x(K2n)=2n-1=△(K2n)(因完全图Kn有2m-1个边不交的匹配) 4)x(G)≥△(G)。(设d(v)=△(G),则与v关联的△(G)条边至少需△(G)种色才 能正常染色)。 引理6.1.1.设G是非空无环的连通图,且不是奇圈,则存在G的边2-染色,使得所用的两 种色在每个度≥2的顶点处都出现 证明:(1)设G是Euer图,则G中无奇度点。 若G本身是一个偶长度圈,则命题显然。若G不是一个偶长度圈,则G至少有一个顶 点w满足d(v0)≥4(否则,G中所有顶点都是2度的,由于G连通,从而G是圈,由引理 条件,G不是奇圈,故为偶圈,矛盾)
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
Δ种色中必有某种色不在u上出现。显然u满足引理6.1.2的条件,因此G中有奇圈。这与 G是二部图矛盾。证毕。 注:也可按推论333,二部图的边集可分解为△(G)个边不交的匹配,故x'(G)=△(G 定理614( Vizing定理,1964)设G是无环非空简单图,则 △(G)≤x(G)≤△(G)+1。 证明:首先,x(G)≥△G)(定义613的注(4))。下证x(G)≤△(G)+1(用反证法) 假如z(G)>△(G)+1,令C=(E1,E2,…,EA)是G的最佳△+1边染色。因 x’>Δ+1,故c必不是正常染色。设u是使c(u)<d(u)的顶点。则必存在色io,o不在u 处出现(因d(u)<△+1),同时也存在色i1,i至少在u处出现两次。设和m1染有颜 色i(如图)。 因d(v1)<△+1,故必有某种色i2不在v处出现。这样i2必然在u处出现(否则,可 用i2给a1重新染色,得到一个改进的△+1边染色,与c是最佳染色矛盾)。因此存在一条 边m2染有色i2 又因d(v2)<△+1,必有某种色i3不在v2处出现。i3必然在a处出现(理由同上)。 因此存在一边a3染有色i3 继续这个过程,可找出一个顶点序列v1,V2…,以及一个颜色序列1,2,…,使得边m 染有颜色小,且色+不在点v处出现,(j=12…)。而且,因c(u)<d(u)且d()是有 限数,故存在一个最小整数m,使得对某个k<m,有im+1=lke 现在,对1≤j≤k-1,用颜色给边m重新染色。这样产生一个新的(△+1)边染色 C=(E1,E2,…,EA+1)。显然对所有v∈,c(v)≥c(v)。因此c’也是G的一个最佳 (△+1)边染色。由引理6.1.2,G[E"∪E]中含有u的那个分支H1是个奇圈 HI
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
§6.2点染色 、点染色的基本概念 定义62.1设G是一个无环边的图。G的顶点正常k染色( proper vertex k- colouring)是指k 种颜色1,2,…,k对于G的各顶点的一种分配,使得任二相邻的顶点被染上不同的颜色。换 句话说,G的顶点正常k染色丌是一个映射 丌:V(G)→{,2,…,k}, 使得丌()是独立集或空集(i=1,2,…,k) 注:设是G的一个顶点正常k染色。令 V1=-(i)={x∈(G)|(x)=l},(i=1,2,…k) 则实际上是对顶点集V(G)的一种划分:x=(V1H2,…,V),其中V∩V,=p U=(G,且每个V是独立集或空集(=1.2…,k) 例如,下图给出了 Petersen图的一种定点正常3染色。 定义62.,2若存在G的一种顶点正常k染色,则称图G是点k色可染的 vertex k-colourable) 有时简称为k色可染的或可k染色的。 注:(1)每个图G一定是U(G)色可染的。 (2)若图G是k色可染的,则对任何正整数m≥k,G也m色可染 定义62.3设G是无环边的图,令 x(G)=min{k|G是k色可染的}, 称x(G)为G的点色数,有时简称为色数( chromatic number)。若x(G)=k,则称G为k色 图( k-chromatic graph)e 注:(1)若x(G)=k(即G是k色图),则G中任何点k染色z=(V1,V2,…,Vk)中每个 V都是非空的独立集。换言之,G的色数是G中点不交的独立集的最小数目 (2)由色数的定义容易证明如下结论 x(G=1分G=K; x(G)=2→G是非空二部图 x(C2n)=3。 x(G)≥3分G含有奇圈
5 §6.2 点染色 一、点染色的基本概念 定义 6.2.1 设 G 是一个无环边的图。G 的顶点正常 k 染色(proper vertex k-colouring)π 是指 k 种颜色12 , ,," k 对于 G 的各顶点的一种分配,使得任二相邻的顶点被染上不同的颜色。换 句话说,G 的顶点正常 k 染色π 是一个映射 π : V (G) → {1,2,", k}, 使得 ( ) 1 i − π 是独立集或空集(i = 1,2,", k). 注:设π 是 G 的一个顶点正常 k 染色。令 V ( ) { ( ) | ( ) } 1 i x V G x i i = = ∈ = − π π ,(i = 1,2,", k )。 则 π 实际上是对顶点集V (G) 的一种划分: ( , , , ) π = V1 V2 " Vk ,其中 Vi ∩Vj = φ , ( ) 1 V V G k i i = = ∪ ,且每个Vi 是独立集或空集(i = 1,2,", k). 例如,下图给出了 Petersen 图的一种定点正常 3 染色。 定义 6.2.2 若存在 G 的一种顶点正常 k 染色,则称图 G 是点 k 色可染的(vertex k-colourable), 有时简称为 k 色可染的或可 k 染色的。 注:⑴ 每个图 G 一定是υ( ) G 色可染的。 ⑵ 若图 G 是 k 色可染的,则对任何正整数m ≥ k ,G 也m 色可染。 定义 6.2.3 设 G 是无环边的图,令 χ(G) = min{k | G 是 k 色可染的}, 称 χ(G) 为 G 的点色数,有时简称为色数(chromatic number)。若 χ(G) = k ,则称 G 为 k 色 图(k-chromatic graph)。 注:(1) 若 χ(G) = k (即 G 是 k 色图),则 G 中任何点 k 染色 ( , , , ) π = V1 V2 " Vk 中每个 Vi 都是非空的独立集。换言之,G 的色数是 G 中点不交的独立集的最小数目。 (2)由色数的定义容易证明如下结论: z χ(G) = 1 ⇔ G K = υ; z χ(G) = 2 ⇔G 是非空二部图; z χ(C2n+1 ) = 3。 z χ(G) ≥ 3 ⇔ G 含有奇圈。 z χ() () G G = υ ⇔ G K ⊇ υ。 1 1 3 3 2 2 3 1 1 2
点染色理论的基本问题:给定图G,确定X(G)的值。 目前,人们仅对某些特殊图类,确定出了计算x(G)的公式。对一般图G,得出了x(G) 的各种上下界。为了介绍有关结果,需要引入色临界图的概念 色临界图 定义62.4设x(G)=k,(k≥1)。若对G的任何真子图H,均有z(H)<k,则称G是临界 k色图( critical k- chromatic graph) 注:临界k色图实际上就是k色极小子图,也就是说,它本身是k色的,但任意删去一个顶 点或一条边后色数就会减少。按色临界图的概念容易知道下列结论成立 x(G)≥3G含有奇圈。 G是临界1色图分→G≡K1; G是临界2色图→G≡K2 ●G是临界3色图◇G是奇圈; 此外,容易证明:(1)任何k色图都包含临界k色子图;(2)每个色临界图都是连通的 简单图。(留作习题)。 定理6.2.1色临界图的顶点割集不是团 证明(反证法):假设图G是一个临界k色图,但有一个点割集S是团。记G\S的连 通分支为G1G2…Gn。将G[S]按G中的连接方式分别与G1,G2…,Gn相连,得到子图 G1,G2,…,Gn 示例:图G及点割集S={uv} 因G是k色临界的,故每个G,是k-1色可染的。由于S是团,所以S中各个顶点在G 的任何k-1染色中必染到相异的色。我们总可以调整各G中颜色的编号,使得S中每一个 顶点在各G′中染相同的色。这些G的染色合在一起便形成G的一个k-1染色。这与G是 临界k色图矛盾。证毕。 推论621每个色临界图都是块(即不含割点,亦即2连通) 证明:假如某临界图不是块,则它有割点。这个割点构成一个团,与定理6.2.1矛盾。证毕。 下一个推论是显然的。 推论622若临界k色图G有2顶点割集{,w},则u与v不相邻
6 点染色理论的基本问题:给定图 G,确定 χ(G) 的值。 目前,人们仅对某些特殊图类,确定出了计算 χ(G) 的公式。对一般图 G,得出了 χ(G) 的各种上下界。为了介绍有关结果,需要引入色临界图的概念。 二、色临界图 定义 6.2.4 设 χ(G) = k,(k ≥ 1) 。若对 G 的任何真子图 H,均有 χ(H) < k ,则称 G 是临界 k 色图(critical k-chromatic graph). 注:临界 k 色图实际上就是 k 色极小子图,也就是说,它本身是 k 色的,但任意删去一个顶 点或一条边后色数就会减少。按色临界图的概念容易知道下列结论成立 z χ(G) ≥ 3 ⇔ G 含有奇圈。 z G 是临界 1 色图⇔ G ≅ K1; z G 是临界 2 色图⇔ G ≅ K2 ; z G 是临界 3 色图⇔G 是奇圈; 此外,容易证明:(1)任何 k 色图都包含临界 k 色子图;(2)每个色临界图都是连通的 简单图。(留作习题)。 定理 6.2.1 色临界图的顶点割集不是团。 证明(反证法):假设图 G 是一个临界 k 色图,但有一个点割集 S 是团。记G \ S 的连 通分支为G G Gn , , , 1 2 " 。将G[S]按 G 中的连接方式分别与G G Gn , , , 1 2 " 相连,得到子图 G G Gn ′, ′, , ′ 1 2 " 。 示例:图 G 及点割集 S={u,v} 1 2 3 G′, G′, G′ 因 G 是 k 色临界的,故每个Gi ′是 k-1 色可染的。由于 S 是团,所以 S 中各个顶点在Gi ′ 的任何 k-1 染色中必染到相异的色。我们总可以调整各Gi ′中颜色的编号,使得 S 中每一个 顶点在各Gi ′中染相同的色。这些Gi ′的染色合在一起便形成 G 的一个 k-1 染色。这与 G 是 临界 k 色图矛盾。证毕。 推论 6.2.1 每个色临界图都是块(即不含割点,亦即 2 连通)。 证明:假如某临界图不是块,则它有割点。这个割点构成一个团,与定理 6.2.1 矛盾。证毕。 下一个推论是显然的。 推论 6.2.2 若临界 k 色图 G 有 2 顶点割集{u, v},则 u 与 v 不相邻。 u v u v u v u v
定理62.2( Dirac,1952)设G是临界k色图(k≥2),则边连通度k'(G)≥k-1。 证明:若k=2,则G≡K2,故K'(G)=1。 下设k≥3,用反证法。 假如k(G)(k-1)2-(k-1)=(k-1k-2)。(注意X与 Y间共可连出(k-1)2条可能的边;其次,因在G中S与S间连边数(k-1)(k-2)矛盾)。由Kong定理(第五章定理522),a(H)=B(H)≥k-1 这表明H有完美匹配(因对于H,X=Y=k-1) 设H的一个完美匹配为M:M={x=1,2…,k-1},相应地V=UU 则v是G的独立集(i=1,2,…,k-1),因此x=(V1,2,…,Vk-1)是G的一个点k1染色 但这与(G)=k矛盾,故x(G)≥k-1。证毕 推论623设G是临界k-色图,则(G)≥k-1。 证明:由定理(G)≥k'(G)≥k(G)及定理622,有(G)≥k(G)≥k-1。证毕。 推论624任何k色图至少有k个顶点的度≥k-1。 证明:设G是k色图,H是其一个临界k色子图,由推论623,H的每个顶点在H中的度 ≥k-1,故在G中的度也≥k-1。由于H是k色临界的,因此它至少有k个顶点。证毕。 三、色数的上下界
7 定理 6.2.2 (Dirac,1952) 设 G 是临界 k 色图(k ≥ 2),则边连通度κ ′(G) ≥ k −1。 证明:若 k = 2,则G ≅ K2 ,故κ ′(G) = 1。 下设k ≥ 3,用反证法。 假如κ′(G) k − − k − = k − k − 。(注意 X 与 Y 间共可连出 2 (k −1) 条可能的边;其次,因在 G 中 S 与 S 间连边数 (k −1)(k − 2) 矛盾)。由 König 定理(第五章定理 5.2.2),α′(H ) = β (H ) ≥ k −1。 这表明 H 有完美匹配(因对于 H, X = Y = k −1)。 设 H 的一个完美匹配为 M* : { 1,2, , 1} * M = x y i = k − i i j " ,相应地 i Vi = Ui ∪Wj , 则 Vi 是 G 的独立集(i = 1,2,", k −1),因此 ( , , , ) π = V1 V2 " Vk−1 是 G 的一个点 k-1 染色。 但这与 χ(G) = k 矛盾,故κ ′(G) ≥ k −1。证毕。 推论 6.2.3 设 G 是临界 k-色图,则δ (G) ≥ k −1。 证明:由定理δ (G) ≥ κ′(G) ≥ κ (G) 及定理 6.2.2,有δ (G) ≥ κ ′(G) ≥ k −1。证毕。 推论 6.2.4 任何 k 色图至少有 k 个顶点的度 ≥ k −1。 证明:设 G 是 k 色图,H 是其一个临界 k 色子图,由推论 6.2.3,H 的每个顶点在 H 中的度 ≥ k −1,故在 G 中的度也≥ k −1。由于 H 是 k 色临界的,因此它至少有 k 个顶点。证毕。 三、色数的上下界 U1 U2 Uk -1 # S W1 W2 Wk-1 # S x1 x2 xk-1 y2 yk-1 y1 # # H
定理62.3对任何简单图G,z(G)≤△(G)+1。 证明:设z(G)=k,且H是G的临界k色子图,由推论6.23,(H)≥k-1。故 △(G)≥△(H)≥(H)≥k-1=x(G)-1。证毕。 定理623给出的上界是可以达到的,例如奇圈和完全图的色数恰好等于它们的最大度 加1。下面来证明,达到这个上界的连通简单图只有这两类图。 定理62.4( Brooks,1941)设G是连通的简单图,且G既不是奇圈又不是完全图,则 x(G)≤△(G)。 证明:设G是满足定理条件的k色图 Casel G本身是临界k色的。 由推论621,G是一个块。又由于临界1色图和临界2色图是完全图,而临界3色图 是奇圈,故k≥4。由推论623,O(G)≥3 如果G是3连通的,则因G不是完全图,故必存在顶点x,y,=∈V(G),使得xE(G) 而x,yz∈E(G),并且G-{x,y}连通。如果G的连通度为2,则G中存在一点z,使得 G-{}有割点且连通,此时G一{}至少有两个连通块只含1个割点(见第二章习题),设 B1、B2为这样两个块因G本身2连通且无割点,故B1、B2均有点在G中与z相邻。设x∈B1 和y∈B2是两个与z相邻的点。由于x1和x2在不同的块中,因此它们在G-{-}中不相邻, 因而在G中也不相邻,且因dQ(=)≥δ(G)≥3,G-{x,y}连通。 总之,必存在顶点x,y,∈V(G),使得xygE(G),x,y2∈E(G)且G-{x,y}连通。 给G的顶点重新编号:首先x1=x,x2=y,然后对G′=G\{x,y中的顶点,按G"中到 的距离由远及近的次序依次用x3,x4…,x编号,即:dG(x1,)≥d(x+1,=), (i=3,4,…,U),(注意G仍连通)。 (x1) >(x2)x7 因此x=2,且对每个=1,2,…U-1,必存在j>i使得xx∈E(G)。由此可知, 对每个i=1,2,…,U-1,x与{x1,x2,…,x21}中最多△(G)-1个顶点相邻(因与x相邻 的至少有一个顶点的下标>1),且因d(z)≥o(G)≥3,故x-1x∈E(G)。 这样一来,可用△(G)种颜色给顶点进行染色:将x1和x2染色1,然后按颜色12,…,Δ 的顺序依次给x3,x4,…,x进行染色,使相邻两点染不同的色。染法为: 设x1,…,x1已染好,考虑x,(3≤i≤U-1)由于x仅与x1,…,x1中最多△(G)-1 个顶点相邻,所以1,2,…,Δ种颜色中至少有一种颜色a在N(x)∩{x1x2,…,xm1}中未
8 定理 6.2.3 对任何简单图 G, χ(G) ≤ Δ(G) +1。 证明:设 χ(G) = k ,且 H 是 G 的临界 k 色子图,由推论 6.2.3, δ (H) ≥ k −1 。故 Δ(G) ≥ Δ(H) ≥ δ (H) ≥ k −1 = χ(G) −1。证毕。 定理 6.2.3 给出的上界是可以达到的,例如奇圈和完全图的色数恰好等于它们的最大度 加 1。下面来证明,达到这个上界的连通简单图只有这两类图。 定理 6.2.4 (Brooks,1941) 设 G 是连通的简单图,且 G 既不是奇圈又不是完全图,则 χ(G) ≤ Δ(G) 。 证明:设 G 是满足定理条件的 k 色图。 Case1. G 本身是临界 k 色的。 由推论 6.2.1,G 是一个块。又由于临界 1 色图和临界 2 色图是完全图,而临界 3 色图 是奇圈,故k ≥ 4 。由推论 6.2.3,δ (G) 3 ≥ 。 如果 G 是 3 连通的,则因 G 不是完全图,故必存在顶点 x, y,z ∈V(G) ,使得 xy ∉ E(G) , 而 xz, yz ∈ E(G) ,并且G {, } − x y 连通。如果 G 的连通度为 2,则 G 中存在一点 z,使得 G {} − z 有割点且连通,此时G {} − z 至少有两个连通块只含 1 个割点(见第二章习题),设 B1、B2 为这样两个块。因 G 本身 2 连通且无割点,故 B1、B2 均有点在 G 中与 z 相邻。设 B1 x ∈ 和 B2 y ∈ 是两个与 z 相邻的点。由于 x1 和 x2在不同的块中,因此它们在G {} − z 中不相邻, 因而在 G 中也不相邻,且因 () ( ) 3 G dz G ≥ ≥ δ ,G {, } − x y 连通。 总之,必存在顶点 x, y,z ∈V(G) ,使得 xy ∉ E(G) , xz, yz ∈ E(G) 且G {, } − x y 连通。 给 G 的顶点重新编号:首先 x = x x = y 1 2 , ,然后对G′ = G \ {x, y}中的顶点,按G′中到 z 的距离由远及近的次序依次用 3 4 x ,,, x x " υ 编号,即: ( , ) ( , ) 1 d x z d x z G′ i ≥ G′ i+ , (i = 3, 4, , " υ ),(注意G′仍连通)。 因此 x z υ = ,且对每个i = − 1, 2, , 1 " υ , 必存在 j > i 使得 ( ) i j x x EG ∈ 。由此可知, 对每个i = − 1, 2, , 1 " υ , i x 与{ , , , } 1 2 i−1 x x " x 中最多 Δ(G) −1个顶点相邻(因与 i x 相邻 的至少有一个顶点的下标> i ),且因d(z) ≥ δ (G) ≥ 3, 故 1 x x EG( ) υ υ − ∈ 。 这样一来,可用 Δ(G) 种颜色给顶点进行染色:将 x1和 x2 染色 1,然后按颜色1,2,",Δ 的顺序依次给 3 4 x ,,, x x " υ 进行染色,使相邻两点染不同的色。染法为: 设 1 1 , , i− x " x 已染好,考虑 xi , ( 3 1 ≤ i ≤ − υ )。由于 xi 仅与 1 1 , , i− x " x 中最多 Δ(G) −1 个顶点相邻,所以1,2,",Δ 种颜色中至少有一种颜色α 在 ( ) { , , , } i 1 2 i−1 N x ∩ x x " x 中未 (x1) x7 x6 x5 x4 x3 (x2) z x9 x y x x8 10
曾用过,因此可给点x染以颜色a。因x,(=2)既与x1又与x2相邻,且x1和x2染的色相同 所以Δ种色中同样也有一种色B在N(x)中未曾用过,(因d(x)≤Δ,而x的邻点中已 有两点染同一种色,故△种色不会全在N(x)中出现)。因此可给x染以色β 如此便得图G的一个正常△-染色,即有:x(G)≤△(G) Case2.G不是k色临界的。此时取G的一个临界k色子图H (1)若H是完全图,则H=Kk,从而 (G)=x(H)=k=(k-1)+1=△(H)+1≤△(G)(G中有不属于H的边和点); (2)若H是一个奇圈,则(G)=(H)=3≤△(G)(G中至少有一条不属于H的边)。 (3)若H既不是完全图,也不是奇圈,则由 Casel的证明可知x(H)≤△(H)≤△(G), 从而x(G)=k=x(H)≤△(G)。 证毕。 例6.2.1求 Peterson图的色数。 解:因 Peterson图G含有奇圈,故不是二部图,因而x(G)≥3 另一方面,G既不是奇圈又不是完全图,且△(G)=3 故(G)≤△G)=3。因此,x(G)=3。 虽然奇圈和完全图可以达到定理623提供的色数上界△(G)+1,但某些图类的色数 这个上界相差很远,比如星图K1n的色数为2,△(Kn)+1=n+1。下面给出的几个上界在 某种程度上是对定理62.3的改进。 定理625设连通简单图G的度序列为d1≥d2≥…≥dn,则 x(G)≤1+ max min(a,i-1} 证明:将G的所有顶点按度的递减(不增)顺序排序,设为v1,"2…,V。从v开始依次给 顶点染色。在第i次染色时,用v;的邻点尚未使用的颜色中色号最小的颜色给v染色(事先 对使用的颜色编号),(i=1,2,…,U)。由于对v染色时,下标比i大的顶点尚未染色,而下 标小于i的顶点中与v相邻的顶点不超过mind1,i-1}个,因此以使用的颜色数也不会超 过min{d,i-1},从而按染色规则,对v染色使用的颜色编号不会超过min{d,-1}+1。 时。这个结论对所有i=1,2,…,U都成立。因此将G的所有顶点全部染色使用的颜色不会 超过 max min{d2,i-1}+1种。证毕 定理625对任何图G,(G)≤1+max(H)。 证明:对于空图,结论显然成立。因此可设(G)=k≥2。 取G的一个临界k色子图H,则(H0)≤maxd(H)。由推论61.3
9 曾用过,因此可给点 i x 染以颜色α 。因 xυ (=z)既与 x1 又与 x2 相邻,且 x1 和 x2 染的色相同, 所以 Δ 种色中同样也有一种色 β 在 N x( υ )中未曾用过,(因 d x( ) υ ≤ Δ ,而 xυ 的邻点中已 有两点染同一种色,故 Δ 种色不会全在 N x( ) υ 中出现)。因此可给 xυ 染以色 β 。 如此便得图 G 的一个正常 Δ -染色,即有: χ(G) ≤ Δ(G) 。 Case2. G 不是 k 色临界的。此时取 G 的一个临界 k 色子图 H。 (1) 若 H 是完全图,则 H= Kk ,从而 χ(G) = χ(H) = k = (k −1) +1 = Δ(H) +1 ≤ Δ(G)(G 中有不属于 H 的边和点); (2) 若 H 是一个奇圈,则 χ(G) = χ(H ) = 3 ≤ Δ(G)(G 中至少有一条不属于 H 的边)。 (3) 若 H 既不是完全图,也不是奇圈,则由 Case1 的证明可知 χ(H) ≤ Δ(H) ≤ Δ(G) , 从而 χ(G) = k = χ(H) ≤ Δ(G) 。 证毕。 例 6.2.1 求 Peterson 图的色数。 解:因 Peterson 图 G 含有奇圈,故不是二部图,因而 χ(G) ≥ 3; 另一方面, G 既不是奇圈又不是完全图,且 Δ(G) = 3, 故 χ(G) ≤ Δ(G) = 3。因此, χ(G) = 3。 虽然奇圈和完全图可以达到定理 6.2.3 提供的色数上界 Δ()1 G + ,但某些图类的色数与 这个上界相差很远,比如星图 K1,n 的色数为 2, 1, (K ) 1 n Δ + = n +1。下面给出的几个上界在 某种程度上是对定理 6.2.3 的改进。 定理 6.2.5 设连通简单图 G 的度序列为 1 2 dd d ≥ ≥≥ " υ ,则 (G) 1 max min{ , 1} i i χ ≤ + − d i 证明:将 G 的所有顶点按度的递减(不增)顺序排序,设为 1 2 vv v ,,, " υ 。从 v1 开始依次给 顶点染色。在第 i 次染色时,用 vi 的邻点尚未使用的颜色中色号最小的颜色给 vi 染色(事先 对使用的颜色编号),( 1, 2, , ) i = " υ 。由于对 vi 染色时,下标比 i 大的顶点尚未染色,而下 标小于 i 的顶点中与 vi 相邻的顶点不超过 min{ , 1} i d i − 个,因此以使用的颜色数也不会超 过 min{ , 1} i d i − ,从而按染色规则,对 vi 染色使用的颜色编号不会超过 min{ , 1} i d i − +1。 时。这个结论对所有i = 1, 2, , " υ 都成立。因此将 G 的所有顶点全部染色使用的颜色不会 超过 max min{ , 1} 1 i i d i − + 种。证毕。 定理 6.2.5 对任何图 G, H G χ(G) 1 max (H) δ ⊆ ≤ + 。 证明:对于空图,结论显然成立。因此可设 χ(G) 2 = k ≥ 。 取 G 的一个临界 k 色子图 H0,则 0 H G δ (H ) max (H) δ ⊆ ≤ 。由推论 6.1.3, 1 1 3 3 2 2 3 1 1 2
x(G)=x(H)=k≤1+6(H)≤1+max(H)。 证毕。 定理62.6用l(G)表示图G中最长路的长度,则(G)≤1+l(G)。 证明:结论对于空图显然成立。因此可设(G)=k≥2。 取G的一个临界k色子图H,由推论623,则O(H)≥k-1。用最长路方法不难证明 H中有长为(H)的路。因此l(G)≥d(H)≥k-1。从而x(G)=k≤1+l(G)。证毕。 关于色数的下界有如下定理。 定理627对任何图G,x(G)≥ 证明:设G的色数是k,则有v(G)的一种划分:丌=(1V2,…Kk),其中V∩v=中 U=(G),且每个V是非空的独立集(=12,…,k)。按分组V,2,…,V的次序将G 的所有顶点依次编号后,其邻接矩阵可写为如下分块形式 AG)=/41 Ak 其中主对角线上每个A都是零矩阵。 设7F=P,则矩阵A(G)中至少有∑P个零元素。另一方面,AG)共有U32个元素但 G只有E条边。由邻接矩阵的对称性,E条边在A(G)中形成2E各非零元素,故A(G)中零 元素的个数应为U2-2E个。由以上两方面,有U2-2E≥∑P2。利用柯西不等式 可∑4)≥(4),有k∑2E)=2。从而02-2已,由此解得 k≥-+1,即x(G)≥ D+1.证毕。 图的色数与独立集和团有关。利用一个图的独立数和团数,可以获得其色数的上下界。 定理628对任何图G,有(1)(G)+a(G)≤U+1,(2)x(G)·a(G)≥U。(a(G)是 G的点独立数) 证明:(1)设I是G的一个最大点独立集,则|I|=a(G)。给I中的点染上一种颜色,G 中其余U-a(G)个顶点每点染一种不同的颜色,这样得到G的一个U-a(G)+1种颜色的 正常染色,因此x(G)≤U-a(G)+1。 (2)设x(G)=k。按定义,Ⅴ(G)可划分为k个非空独立集V,V2…,V,则 a(G)2V|,1=1,2…,k。从而ka(G)≥∑|=D,即x(G)a(G)≥U
10 0 0 H G χ(G) (H ) 1 (H ) 1 max (H) χδ δ k ⊆ = = ≤+ ≤+ 。 证毕。 定理 6.2.6 用l(G) 表示图 G 中最长路的长度,则 χ(G) 1 (G) ≤ + l 。 证明:结论对于空图显然成立。因此可设 χ(G) 2 = k ≥ 。 取 G 的一个临界 k 色子图 H,由推论 6.2.3,则δ (H) 1 ≥ − k 。用最长路方法不难证明, H 中有长为δ (H) 的路。因此l(G) ≥ ≥− δ (H) 1 k 。从而 χ(G) 1 (G) = k l ≤ + 。证毕。 关于色数的下界有如下定理。 定理 6.2.7 对任何图 G, 2 2 (G) 1 ε χ υ ⎡ ⎤ ≥ + ⎢ ⎥ ⎢ ⎥ 证明:设 G 的色数是 k,则有V (G) 的一种划分: ( , , , ) π = V1 V2 " Vk ,其中Vi ∩Vj = φ , ( ) 1 V V G k i i = = ∪ ,且每个Vi 是非空的独立集(i = 1,2,", k)。按分组 1 2 ,,, VV V " k 的次序将 G 的所有顶点依次编号后,其邻接矩阵可写为如下分块形式 11 12 1 21 22 2 1 2 A(G) k k k k kk AA A AA A AA A ⎛ ⎞ ⎜ ⎟ = ⎝ ⎠ " " " """ " 其中主对角线上每个 Aii 都是零矩阵。 设| | V p i i = ,则矩阵 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 i i ii ii i a b ab == = ∑∑ ∑≥ ,有 k ⋅ 2 1 k i i p = ∑ ≥ 2 2 1 ( ) k i i p υ = ∑ = 。从而 2 υ − 2ε ≥ 2 k υ 。由此解得 2 2 k 1 ε υ ≥ + ,即 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 ,,, VV V " k ,则 (G) | | α ≥ Vi ,i k = 1, 2, , " 。从而 1 () | | k i i kG V α υ = ≥ = ∑ ,即 χ(G) (G) ⋅α υ≥