文档介绍：本次课主要内容
(一)、相关概念
(二)、图的点色数的几个结论
(三)、四色与五色定理
图的顶点着色
(四)、顶点着色的应用
*
第一页，共三十八页。
跟图的边着色问题一样，生活中的很多问题，可以模型为图的顶点着色问题来鲁克斯，1941) 若G是连通的单图，并且它既不是奇圈，又不是完全图，则：
数学家罗瓦斯在1973年给出了如下证明。
证明：不失一般性，我们可以假设G是正则的，2连通的，最大度Δ≥3的简单图。原因如下：
(1) 容易证明：若G是非正则连通单图，最大度是Δ，则
事实上，我们可以对G的顶点数作数学归纳证明：
*
第十三页，共三十八页。
当n=1时，结论显然成立；
设对于阶数小于n的简单非正则连通单图来说，结论成立。下设G是阶数为n的非正则连通单图。
设u是G中顶点，且d(u)=δ<Δ，考虑G1=G-u
若G1是正则单图，则Δ(G1)=Δ(G)-1。于是G1是可Δ(G)顶点正常着色的，从而，G是可Δ(G)正常顶点着色的；
若G1是非正则单图，则由数学归纳，G1是可Δ(G)顶点正常着色的，从而，G是可Δ(G)正常顶点着色的。
(2) 容易证明：若G是1连通单图，最大度是Δ，则
*
第十四页，共三十八页。
(3) Δ(G) ≤2
由条件， G只可能为偶圈。所以定理结论显然成立。
所以，下面只需证明：假设G是正则的，2连通的，最大度Δ≥3的简单图，且不是完全图或奇圈，有：
分两步完成证明。
1) 在上面条件下，我们证明：G中存在三点x1, x2, xn,使得G -｛x1, x2｝连通，x1与x2不邻接，但x1, x2与xn均邻接；
x1
x2
xn
G
*
第十五页，共三十八页。
情形1 设G是3连通的正则非完全图。
对于G中点xn, 显然在其邻点中存在两个不邻接顶点x1与x2, 使得G-｛x1, x2｝连通。
情形2 设G是连通度为2的正则非完全图。
此时，存在点xn,使得G-xn连通且有割点v, 于是G-xn至少含有两个块。
v
G -xn
块
块
块
*
第十六页，共三十八页。
由于G本身2连通，所以G-xn的每个仅含有一个割点的块中均有点与xn邻接。设分属于H1与H2中的点x1与x2，它们与xn邻接。由于x1与x2分属于不同块，所以x1与x2不邻接。又显然G-｛x1, x2｝连通。
2) 对G中顶点进行如下排序：
令xn-1 ∈V(G)-｛x1, x2, xn｝且与xn邻接；
xn-2 ∈V(G)-｛x1, x2, xn，xn-1｝且与xn或xn-1邻接；
xn-3 ∈V(G)-｛x1, x2, xn，xn-1,xn-2｝且与xn或xn-1或xn-2邻接；
不断这样作下去，可得到G的顶点排序：x1,x2,…,xn
*
第十七页，共三十八页。
该顶点序列的特征是，对于1≦i≦n-1,xi与某个xi+k邻接。
把着色算法用于G，按照上面顶点排序着色，容易知道，用Δ(G)种颜色可以完成G的正常点着色。
对于简单图的点色数，还可以在定理2的基础上获得改进。
定义3 设G是至少有一条边的简单图，定义：
其中N(u)为G中点u的邻域。称Δ2(G)为G的次大度。
*
第十八页，共三十八页。
如果令：
那么，
例如：求下面图的次大度Δ2(G)
G1
G2
*
第十九页，共三十八页。
解：(1)
G1
v5
v4
v3
v2
v1
G2
v5
v4
v3
v2
v1
v8
v7
v6
v9
(2)
*
第二十页，共三十八页。
G2
v5
v4
v3
v2
v1
v8
v7
v6
v9
注：由次大度的定义知：Δ2(G)≦Δ(G)
定理3 设G是非空简单图，则：
注：定理3是对定理2的一个改进！
*
第二十一页，共三十八页。
G2
v5
v4
v3
v2
v1
v8
v7
v6
v9
例如：对下面单图来说，由定理2得：
而由定理3得：
推论：设G是非空简单图，若G中最大度点互不邻接，则有：
*
第二十二页，共三十八页。
1、四色定理
(三)、四色与五色定理
1852年，刚毕业于伦敦大学的格斯里(1831—1899)发现：给一张平面地图正常着色，至少需要4种颜色。这就是著名的4色定理。
格斯里把他的证明通过他弟弟转交给著名数学家摩尔根，引起摩尔根极大兴趣并于当天给数学家哈密尔顿写了封相关信件。但没有引起哈密尔顿的注意。
直到1878年，在英国数学会议上，数学家凯莱才再一次提到4色问题。
*
第二十三页，共三十八页。
1879年7月，业余数学家肯普(1849---1922）在英