图的染色上课讲义.ppt

《图的染色上课讲义.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图的染色例子若图G是k边可染的，而l＞k，则G也是l边可染的。使图G具有正常边染色的最小颜色数，称为G的边色数，记作χ’(G)。χ’(G)≥Δ(G)引理6.1设连通图G不是长度为奇数的回路，则G有一个2边染色，它的两种颜色在度至少为2的每个顶点都出现。证首先假设连通图G是Euler图。如果G的所有顶点度数均为2，那么G是回路。故G是长度为偶数的回路，此时定理显然成立。如果G的顶点度数不全是2，那么必有一个度数至少为4的顶点v。设e1e2…eq是G的Euler环游。令E1={ei

2、i是奇数}，E2={ei

3、i是偶数}。因为G的每个顶

4、点都是环游的内部顶点，所以G的2边染色(E1,E2)具有所要求的性质。其次，假设G不是Euler图，那么添加一个新的顶点w，并把它和G的每一个奇顶点都连接起来，这样构成的图G*显然是Euler图。we1e2…eqw是G*的Euler环游，同上面一样定义E1,E2。则(E1∩E,E2∩E)具有所要求的性质。最优k边染色给定图G的一个k边染色α之后，我们用Cα(v)表出在染色α下点v所出现的不同颜色的数目，显然有Cα(v)≤dG(v)，并且等号对所有顶点成立当且仅当α是正常k边染色。设图G有两个k边染色α和β，若有则称k边染色α优于β

5、，如果不存在优于α的k边染色，就说α是最优的k边染色。引理6.2设α是图G的一个最优的k边染色。若存在G中的一个顶点u及两种颜色i和j，使得i不在u出现，而j至少在u出现两次。令Ei和Ej分别为G中以i和j着色的边的集合，则G[Ei∪Ej]中含有u的分支B是长度为奇数的回路。定理6.3对于任何简单图G有Δ(G)≤χ’(G)≤Δ(G)+1证假设对于简单图G，有χ’(G)＞Δ(G)+1，令α是一个最优(Δ(G)+1)边染色，必有顶点u适合Cα(u)＜dG(u)，又dG(u)＜Δ(G)+1，因此按照α染色必有颜色i0在u不出现，而i1在

6、u至少出现两次。设α(u,v)=i1，α(u,v1)=i1，因为dG(v1)=Δ(G)+1，所以有颜色i2在v1不出现，但i2必定出现。否则就可以把(u,v2)改用颜色i2，得到一个新的Δ(G)+1边染色优于α。这与对α的假设矛盾。又设α(u,v2)=i2，同上理由，有颜色i3在v2不出现而在u必出现，否则可以把(u,v1)改用i2染色，把(u,v2)改用i3染色，于是得到另一个Δ(G)+1边染色优于α，引出矛盾。继续这个过程，构造出一个顶点序列v1,v2,…和一个颜色序列i1,i2,…，vi均与u邻接，使得vt均与u邻接，α(u

7、,vt)=it，it+1不在vt出现(t=1,2,…,i)。由于dG(u)有限，因此有最小整数l，使得存在k

8、β(e)=i0,e∈E(G)}，Eik={e

9、β(e)=ik,e∈E(G)}。由引理6.2，G[Ei0∪Eik]中包含u的分支B是一个长度为奇数的回路。由此可知对于边染色α，v

10、k恰与G[Ei0∪Eik]的两条边关联，即vk在此导出子图中度为2。又定义G的另一个(Δ(G)+1)边着色γ:γ(u,vt)=vt+1(t=1,2,…,l)，对其它e∈E(G),γ(e)=α(e)。显然，对于任何v∈V(G)有Cγ(v)＞Cα(v)，因此γ也是一个最优(Δ(G)+1)边染色，令E’i0={e

11、γ(e)=i0,e∈E(G)}，E’ik={e

12、γ(e)=ik,e∈E(G)}。则G[E’i0∪E’ik]中包含u的分支B’是一个长度为奇数的回路。比较回路B中各边在与下的染色，只有(u,vk)改变了颜色，因此vk在G[E’i

13、0∪E’ik]中的度数为1，这与B’是奇回路矛盾，因此推知定理成立。定理6.4二分图属于第一类图，即χ’(G)=Δ(G)证G为二分图，假定χ’(G)=Δ(G)+1，设α是一个最优边染色，必有顶点u适合Cα(u)＜dG(u)。u显然满足引理6.2的条件，所以G包含一个长度为奇数的回路。因而不是二分图，导出矛盾。故χ’(G)=Δ(G)+1，χ’(G)=Δ(G)定理6.5若图G中任一对顶点之间的边的重数最多为n，则Δ(G)≤χ’(G)≤Δ(G)+n练习1、证明：χ’(K2n-1)=χ’(K2n)=2n-1证明：将K2n中2n-1个点安排

14、在一个正2n-1边形顶点上，v0位于这正多边形的中心。对任一i，取v0vi边，以及vi-kvi+k，其中顶点的足标理解成模2n-1的同余。显然这些边构成K2n的一个完美匹配Fi，且i≠j时，Fi与Fj的边不相交，K2n=F1∪F2∪…∪F2n-1对