解：一方面，由图的结构特征容易知道（©）≥4 另一方面，通过具体着色，用4种颜色可以得到该图的 一种正常点着色，则：zG)≤4 GT MA。 G AC 所以，(G)=4
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 6 解：一方面，由图的结构特征容易知道 ( ) 4 G 另一方面，通过具体着色，用4种颜色可以得到该图的 一种正常点着色，则： ( ) 4 G GT MA G AC LA S 所以， ( ) 4 G =
注：对图的正常顶点着色，带来的是图的顶点集合的 一种划分方式。所以，对应的实际问题也是分类问题。 属于同一种颜色的顶点集合称为一个色组，它们彼此不 相邻接，所以又称为点独立集。用点色数种颜色对图G 正常着色，称为对图G的最优点着色。 定义2色数为k的图称为k色图。 二)、图的点色数的几个结论 定理1对任意的图G,有：(G)≤△(G)+口 分析：事实上，定理结论容易想到，因为任意一个顶点 度数至多为△，因此，正常着色过程中，其邻点最多用去△ 种颜色，所以，至少还有一种色可供该点正常着色使用
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 7 注：对图的正常顶点着色，带来的是图的顶点集合的 一种划分方式。所以，对应的实际问题也是分类问题。 属于同一种颜色的顶点集合称为一个色组，它们彼此不 相邻接，所以又称为点独立集。用点色数种颜色对图G 正常着色，称为对图G的最优点着色。 定义2 色数为k的图称为k色图。 (二)、图的点色数的几个结论 定理1 对任意的图G，有： ( ) ( ) 1 G G + 分析：事实上，定理结论容易想到，因为任意一个顶点 度数至多为Δ，因此，正常着色过程中，其邻点最多用去Δ 种颜色，所以，至少还有一种色可供该点正常着色使用
证明：我们对顶点数作数学归纳证明。 当n=1时，结论显然成立。 设对顶点数少于的图来说，定理结论成立。考虑一般 的n阶图G。 任取v∈V(G),令G1=G-v,由归纳假设： X(G)≤△(G)+1≤△(G)+1 设Ⅱ是G,的一种△(G)+1正常点着色方案，因为v的邻点 在π下至多用去△(G)种色，所以给v染上其邻点没有用过 的色，就把扩充成了G的△(G)+1着色方案。 对于G来说，可以给出其△(G)+1正常点着色算法
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 8 证明：我们对顶点数作数学归纳证明。 当n=1时，结论显然成立。 设对顶点数少于n的图来说，定理结论成立。考虑一般 的n阶图G。 任取v ∈V(G), 令G1=G-v， 由归纳假设： 1 1 ( ) ( ) 1 ( ) 1 G G G + + 设п是G1的一种Δ(G)+1正常点着色方案，因为v的邻点 在п下至多用去Δ(G)种色，所以给v染上其邻点没有用过 的色，就把п扩充成了G的Δ(G)+1着色方案。 对于G来说，可以给出其Δ(G)+1正常点着色算法
G的△(G)+1正常点着色算法 设G=(V,E),V=(V1Y2Vn),色集合C={1,2,△+1}， 着色方案为π。 (1)令Π(v)=1,i=1: (2)若=n,则停止；否则令： C(y)={π(y,)j≤i,并且v,与y,+相邻} 设k为C-C(y+1)中的最小整数，令 π(y,+)=k (3)令=i+1,转(2)
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 9 G的Δ(G)+1正常点着色算法 设G=(V, E), V=｛v1 ,v2 ,.,vn｝,色集合C=｛1,2,.,Δ+1｝, 着色方案为п。 (1) 令п(v1)=1, i=1; (2) 若i=n,则停止；否则令： C v v j i v v ( ) ( ) , i j j i + + 1 1 = 并且 与 相邻 设k为C-C(vi+1)中的最小整数，令 +1 ( )= i v k (3) 令i=i+1,转(2)
例2给出下图的△+1正常点着色。 解：色集C={1,2,3,4,5} (1),π(y)=1 (2),C(2)={1},C-C(y2)={2,3,4,5},k=2 (1),(2)=2 (2),C(y3)={1,2},C-C(y3)={3,4,5},k=3 10
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 10 例2 给出下图的Δ+1正常点着色。 v5 v4 v3 v2 v1 v6 解：色集C=｛1, 2, 3, 4, 5｝ 1 (1), ( )=1 v (2), ( )= 1 , ( ) 2,3,4,5 , 2 C v C C v k 2 2 − = = 2 (1), ( )=2 v (2), ( )= 1,2 , ( ) 3,4,5 , 3 C v C C v k 3 3 − = =