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

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

7 定理 6.2.2 (Dirac,1952) 设 G 是临界 k 色图（k ≥ 2），则边连通度κ ′(G) ≥ k −1。证明：若 k = 2，则G ≅ K2 ，故κ ′(G) = 1。下设k ≥ 3，用反证法。假如κ′(G) < k −1 ，则存在 S ⊂ V(G) 使得| (S, S ) |= κ ′(G) < k −1。因 G 是临界 k 色图，故 [ ] 1 G = G S 与 [ ] G2 = G S 中的顶点都 k −1 色可染。设 ( , , , ) π 1 = U1 U2 " Uk−1 和 ( , , , ) π 2 = W1 W2 " Wk−1 分别是G1 和G2 中点的k −1染色。构造二部图 H = (X,Y ), { , , } = 1 2, k−1 X x x " x , { , , } = 1 2, k−1 Y y y " y , 其中 xi i y j ∈ E(H ) ⇔ U 的点与Wj 的点在 G 中无连边。因| (S, S ) |= κ ′(G) < k −1, 故 ( ) ( 1) ( 1) ( 1)( 2) 2 ε H > k − − k − = k − k − 。（注意 X 与 Y 间共可连出 2 (k −1) 条可能的边；其次，因在 G 中 S 与 S 间连边数< k −1，故 X 与 Y 间在 H 中不能连的边数< k −1）。我们来证明 H 必有完美匹配。事实上，H 的点覆盖数 β (H) ≥ k −1（否则，若 β (H) ≤ k − 2，则因 Δ(H) ≤ k −1, H 的每个顶点至多能覆盖 k −1 条边。这样 ε (H) ≤ β (H)⋅(k −1) ≤ (k − 2)(k −1) ，与 ε (H) > (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

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) ⋅α υ≥

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

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