本次课主要内容 与色数有关的几类图和完美图 (一)、与色数有关的几类图 (二)、完美图简介
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 2 本次课主要内容 (一)、与色数有关的几类图 (二)、完美图简介 与色数有关的几类图和完美图
(一)、与色数有关的几类图 1、临界图 定义1若对图G的任意真子图H,都有H)<G，则 称G是临界图。点色数为k的临界图称为k临界图。 3临界图 非临界图 4临界图 注：临界图由狄拉克在1952年首先提出并研究。上面 的4临界图是Grotzsch(格勒奇)在1958年提出的
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 3 1、临界图 (一)、与色数有关的几类图 定义1 若对图G的任意真子图H，都有 ，则 称G是临界图。点色数为k的临界图称为k临界图。 ( ) () H G 3临界图 4临界图 非临界图 注：临界图由狄拉克在1952年首先提出并研究。上面 的4临界图是Grotzsch(格勒奇)在1958年提出的
定理1临界图有如下性质 (1)k色图均有k临界子图； (2)每个临界图均为简单连通图； (3)若G是k临界图，则6≥k-1。 证明：(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 4 定理1 临界图有如下性质 (1) k色图均有k临界子图； (2) 每个临界图均为简单连通图； (3) 若G是k临界图，则δ≥k-1。 证明： (1)是显然的。 (2) 因为删掉环或平行边中的一条边并不破坏原有的顶 点正常着色，所以每个临界图是单图；又因为删掉色数 较小的分支，剩下部分的图的色数和原图色数相等，所 以，临界图必须是连通图
(3)若不然，8<k-1。 设d(w)=δ。因为G是k临界图，所以G-v是k-1可正常顶 点着色的。设n是G-v的k-1正常顶点着色方案，显然， 它可以扩充为G的k-1正常点着色方案。这与G是k临界图 相矛盾。 推论：每个k色图至少有k个度不小于k-1的顶点。 证明：因G是k色图，所以，它包含k临界子图G所以 有：8(G)≥k-1,即G中至少有k个顶点，其度数不小于 k-1。所以，G中至少有k个度不小于k-1的顶点。 例1利用上面推论证明：对任意图G,有： X(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 5 (3) 若不然，δ< k-1。 设d(v)=δ。因为G是k临界图，所以G-v是k-1可正常顶 点着色的。设п是G-v的k-1正常顶点着色方案，显然， 它可以扩充为G的k-1正常点着色方案。这与G是k临界图 相矛盾。 推论：每个k色图至少有k个度不小于k-1的顶点。 证明：因G是k色图，所以，它包含k临界子图G1,所以 有：δ(G1)≥k-1,即G1中至少有k个顶点，其度数不小于 k-1。所以，G中至少有k个度不小于k-1的顶点。 例1 利用上面推论证明：对任意图G，有： () ()1 G G
证明：设G的点色数为 。由推论，G中至少有 x(G》 个顶点，其度数不小于 x(G)-1 所以，A(G)≥X(G)-I,即：(G)≤△(G)+1 例2求证：临界图没有割点。 证明：设G是k临界图。如果G有割点y设G1,G2,,G,是 G-v的分支。又设第i个分支顶点集为V,(I≤i≤r)。 设H=GV,U{v}],(1ir)。则H是k-1可正常点着色 的，现对每个H进行k-1正常点着色，且v都分配同一种颜色， 那么，将着色后的H合在一起，得到G的k-1正常点着色方 案，这与G是k色图矛盾。所以临界图没有割点
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 证明：设G的点色数为 。由推论，G中至少有 个顶点，其度数不小于 () ()1 G G ( ) G ( ) G ()1 G 所以， ，即： () ()1 G G 例2 求证：临界图没有割点。 证明：设G是k临界图。如果G有割点v, 设G1,G2,…,Gr是 G-v的分支。又设第i个分支顶点集为Vi (1≦i≦r)。 设Hi=G[Vi∪｛v｝], (1≦i≦r)。则Hi是k-1可正常点着色 的，现对每个Hi进行k-1正常点着色，且v都分配同一种颜色， 那么，将着色后的Hi合在一起，得到G的k-1正常点着色方 案，这与G是k色图矛盾。所以临界图没有割点