(1),π(3)=3 (2),C(v4={3},C-C(y4)={1,2,4,5},k-1 (1),π(y4)=1 (2),C(y)={1},C-C(y)={2,3,4,5},k=2 (1),π(y)=2 (2),C(y6)={1,2,3},C-C(vs)={4,5},k=4 (1),π(v6)=4 V6(4) V(1) vs(2) V2(2 v3(3)
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 11 v5 v4 v3 v2 v1 v6 3 (1), ( )=3 v (2), ( )= 3 , ( ) 1,2,4,5 , 1 C v C C v k 4 4 − = = 4 (1), ( )=1 v (2), ( )= 1 , ( ) 2,3,4,5 , 2 C v C C v k 5 5 − = = 5 (1), ( )=2 v (2), ( )= 1,2,3 , ( ) 4,5 , 4 C v C C v k 6 5 − = = 6 (1), ( )=4 v v5 (2) v4 (1) v3 (3) v2 (2) v1 (1) v6 (4)
注：(1)不能通过上面算法求出色数，例如，根据上面算法， 我们求出了一个4色方案，但G是3色图： s (2)Velsh一Powelli稍微对上面算法做了一个修改，着色时 按所谓最大度优先策略，即使用上面算法时，按顶点度数由 大到小的次序着色。这样的着色方案起到了对上面算法的 个改进作用。 12
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 12 v5 v4 v3 v2 v1 v6 注: (1)不能通过上面算法求出色数，例如，根据上面算法， 我们求出了一个4色方案，但G是3色图： (2) Welsh—Powell稍微对上面算法做了一个修改，着色时 按所谓最大度优先策略，即使用上面算法时，按顶点度数由 大到小的次序着色。这样的着色方案起到了对上面算法的一 个改进作用
对于简单图G来说，数学家布鲁克斯Brooks)给出了 一个对定理1的色数改进界。这就是下面著名的布鲁克 斯定理。 定理2（布鲁克斯，1941）若G是连通的单图，并且它 既不是奇圈，又不是完全图，则：x(G)≤A(G) 数学家罗瓦斯在1973年给出了如下证明。 证明：不失一般性，我们可以假设G是正则的，2连 通的，最大度△≥3的简单图。原因如下： (1)容易证明：若G是非正则连通单图，最大度是△， 则(G)≤A(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 13 对于简单图G来说，数学家布鲁克斯(Brooks)给出了 一个对定理1的色数改进界。这就是下面著名的布鲁克 斯定理。 定理2(布鲁克斯，1941) 若G是连通的单图，并且它 既不是奇圈，又不是完全图，则： ( ) ( ) G G 数学家罗瓦斯在1973年给出了如下证明。 证明：不失一般性，我们可以假设G是正则的，2连 通的，最大度Δ≥3的简单图。原因如下： (1) 容易证明：若G是非正则连通单图，最大度是Δ， 则 ( ) ( ) G G 事实上，我们可以对G的顶点数作数学归纳证明：