图的染色

图的染色四川师范大学数学与软件科学学院周思波边染色给定(p,q)图，考虑用k种颜色对G的q条边进行染色。这就是，把G的边集E(G)划分为k个子集Ei，Ei称为第i个色组，其中的边被认为染上了第i种颜色。实际上就是由G的边集E(G)到色集S={1,2,…,k}建立一个映射α。如果对于G的任何两条相邻的边ei,ej，都有α(ei)≠α(ej)，换句话说，对每个i，Ei都是图G的边无关集，那么α就称为G的一个正常k边染色。若图G有正常的k边染色，则称G为k边可染的。例子e5e6e4e2e3e1e8e7e9e10v6v1v2v3v5v4若图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|i是奇数}，E2={ei|i是偶数}。因为G的每个顶点都是环游的内部顶点，所以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边染色α和β，若有)()()()(GVvGVvvCvC则称k边染色α优于β，如果不存在优于α的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在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,vt)=it，it+1不在vt出现(t=1,2,…,i)。由于dG(u)有限，因此有最小整数l，使得存在kl，有il+1=ik现给出G的一个新的染色β：令β(u,vt)=vt+1(t=1,2,…,k-1)，对其它e∈E(G),β(e)=α(e)。显然，对于任何v∈V(G)有Cβ(v)≥Cα(v)，因此β也是一个最优(Δ(G)+1)边染色，令Ei0={e|β(e)=i0,e∈E(G)}，Eik={e|β(e)=ik,e∈E(G)}。由引理6.2，G[Ei0∪Eik]中包含u的分支B是一个长度为奇数的回路。由此可知对于边染色α，vk恰与G[Ei0∪Eik]的两条边关联，即vk在此导出子图中度为2。i1i1i2ilik-1ikuv1vv2vlvk-1vki2i1i3ilikikBuv1vv2vlvk-1vk又定义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|γ(e)=i0,e∈E(G)}，E’ik={e|γ(e)=ik,e∈E(G)}。则G[E’i0∪E’ik]中包含u的分支B’是一个长度为奇数的回路。比较回路B中各边在与下的染色，只有(u,vk)改变了颜色，因此vk在G[E’i0∪E’ik]中的度数为1，这与B’是奇回路矛盾，因此推知定理成立。i2i1i3ilikikBuv1vv2vlvk-1vki2i1i3ikikik+1B'uv1vv2vlvk-1vk定理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个点安排在一个正2n-1边形顶点上，v0位于这正多边形的中心。对任一i，取v0vi边，以及vi-kvi+k，其中顶点的足标理解成模2n-1的同余。显然这些边构成K2n的一个完美匹配Fi，且i≠j时，Fi与Fj的边不相交，K2n=F1∪F2∪…∪F2n-1对每一个完美匹配着以不同的颜色，按定义这种着色是正常的，故χ’(K2n)≤2n-1，又χ’(K2n)≥Δ(K2n)=2n-1，所以χ’(K2n)=2n-1把上图中的中心点及关联边去掉，则我们得到一个图，且从原来在中的正常的2n-1-边着色得到中的一个正常的2n-1-边着色。故χ’(K2n-1)≤2n-1，另一方面由于中共有2n-1个顶点，故它的任一个正常的边着色的每一色类至多含n-1条边，而共有(2n-1)(n-1)条边，从而χ’(K2n-1)≥2n-1所以χ’(K2n-1)=2n-1习题2、找一个适当的边染色以证明χ’(Km,n)=Δ(Km,n)证设m≥n，于是Δ(Km,n)=m，令X={x1,x2,…,xm}，Y={y1,y2,…,yn}。设0,1,…,m-1是m种颜色，我们在xiyj边上着以(i+j)mod(m)色，显然这种m-边着色是正常的，从而我们有χ’(Km,n)≤Δ(Km,n)。另一方面，对任意G恒有χ’(G)≥Δ(G)，故χ’(Km,n)=Δ(Km,n)y1x1y2x2y3x3x4习题3、证明petersen图的边色数为4。练习4、证明：若G是奇数阶的正则简单图，且q0，则χ’(G)=Δ(G)+1证明：因为p为奇数，故G的任一正常的边着色的每一色类最多是(p-1)/2条边，从而χ’(G)(p-1)/2≥q又G为正则图，从而q=Δ(G)p/2故χ’(G)Δ(G)由Vizing定理χ’(G)≤Δ(G)+1故χ’(G)=Δ(G)+1点染色类似的，把G的顶点集V(G)划分成k个子集Vi(i=1,2,…,k)，Vi称为第i个色组，其中的点被认为染上了第i种颜色，称为i色点。也可以说，由点集V(G)到颜色集S={1,2,…,k}建立了一个映射β,Vi=β-1(i)。如果在某个k点染色β中，任何两个同色点都不相邻，即每个Vi都是点独立集，那么这个β就称为正常k-点染色。若图G有正常k点染色，则称G为k点可染的，简称为k可染色。例子使G具有正常点染色的最小颜色数，称为G的点色数，记作χ(G)。若χ(G)=k，则把G称为k色图。显然，G是p阶完全图当且仅当χ(G)=p，G是二分图当且仅当χ(G)=2。e5e6e4e2e3e1e8e7e9e10v6v1v2v3v5v4定理6.6对于任何p阶图G，χ(G)+α(G)≤p+1，χ(G)·α(G)≥p证明设S是G的一个最大点独立集，|S|=α(G)，令S中的点染第1色，V(G)中其余p-α(G)个点分别染第2,3,…,p-α(G)+1色，这样得到G的一个正常p-α(G)+1点染色，于是χ(G)+α(G)≤p+1设χ(G)=k，则V(G)可以划分成k个色组V1,V2,…,Vk，由于每个色组均为点独立集，所以|Vi|≤α(G)，故p=Σ|Vi|≤kα(G)=χ(G)·α(G)临界图如果对于图G的每个真子图H都有χ(H)＜χ(G)，则G就称为临界图。显然临界图是连通的。定理6.7任何图G都含有临界的导出子图H，使χ(H)=χ(G)。定理6.8若G是k色的临界图，则k≤δ(G)+1推论6.9每个k色图G至少有k个度不上于k-1的顶点。推论6.10对任意图G，有χ(G)≤Δ(G)+1推论6.11临界图的顶点割不是团。推论6.12每个临界图都是块。定理6.13若连通图G既不是奇回路，又不是完全图，则χ(G)≤Δ(G)对Petersen图应用上述结果，得到χ(G)≤3定理6.14对于(p,q)图G，有χ(G)≥[2q/p2]+1证设图G是k点可染的，那么V(G)可划分成k个色组V1,V2,…Vk，每组内的顶点互不相邻。因此适当选择顶点编号后，G的邻接矩阵A(G)可写成如下的分块形式kkkkkkAAAAAAAAAGA212222111211)(设|Vi|=pi，则A(G)中至少有个元素为零。又因G有kiip12q条边，所以A(G)中零元素为(p2-2q)个，故有kiipqp1222其中所有Aii均为零矩阵。对k维向量(p1,p2,…,pk)和(1,1,…,1)应用柯西不等式得22112pppkkiikii故kpqp222解得122pqk所以12)(2pqG对Petersen图应用上述结果，得到χ(G)≥2练习1、若G是简单图，则χ≥p2/(p2-2q)证明：V(G)可以分划成χ个独立集。设第i个独立集的元素个数记为ni，则1iipn1221)(2iiiiinpnpnq2122)(2pnqpii所以，χ≥p2/(p2-2q)练习2、证明：若G的任意两个长度为奇数的圈都有一个公共顶点，则χ≤5证：若χ≥6，且假定在G上已有χ种颜色着色。令G1是G中着1,2,3色的顶点在G中的导出子图，G2是G中着4,5,色的顶点在G中的导出子图。显然χ(G1)=3，χ(G2)=χ-3≥3，由于二分图的色数均为2，故G1、G2均不是二分图，所以在G1、G2中均含有奇圈且它们互不相交。这和假设矛盾。故χ≤5练习3、证明：唯一的1临界图是K1，唯一的2临界图是K2，仅有的3临界图是k≥3的奇k圈。证：由于1-色图是空图，从而1-临界图只能是K1；2-色图是二分图，从而2-临界图仅能是K2；3-色图恒含奇圈。且奇圈至少是3-色才能正常着色，从而3-临界图仅能是k-奇圈(k≥3)色多项式设G是p个顶点标定的完全图，用t种颜色对G的顶点进行染色。当tp，G不存在t-正常染色。当t≥p，对G进行t-正常染色的方法数为t(t-1)(t-2)…(t-p+1)。设G是由p个孤立点构成的标定图，那么对G进行t-正常染色的方法数为tp。一般地，对于给定的p阶标定图G，对其进行t-正常染色的方法数是t的一个函数，可以表示成t的一个多项式，称为图G的色多项式，记为f(G,t)。给定图G，设u,v∈V(G)，e=(u,v)∈E(G)，对于G-e进行t-正常染色，这种染色分为两类：一类是u,v颜色不同，它与图G的正常染色是一一对应的；另一类是