关于图g的色数和色色交换

关于图g的色数和色色交换

1840年，数学家莫奥贝茨提出了一张面积为四英寸的平面地图，假设相邻两个国家有不同的颜色。这个假设被称为灰色假设。1879年A.B.Kempe曾发表论文,声称证明了四色猜想。11年后,P.J.Heawood指出Kempe证明为错。许多数学家企图证明四色猜想,但都未成功,直至1976年美国K.I.Appel和W.Hakem借助于电子计算机证明了四色猜想为真。本人于1998年从理论上证明了A(Q)类平面图可4-着色。近数年内作者对平面图及其着色的研究取得了一些成果。在上述基础上,本人将从理论上证明任一平面图可4-着色。1kempe法色交换的可能性令χ(G)为图G的色数。设图G用a1,a2,…,aχ(G)等χ(G)种颜色着色。在G中,由分别着ai(i=1,2,…,χ(G))色的点与aj(j=1,2,…,χ(G);i≠j)色的点以及它们之间的边所构成的子图称为G的aiaj的两色子图,记为Gaiaj。Gaiaj可能是连通的,也可能是分离的。若两色连通子图Gaiaj中包含点υk,则将它记为Gaiaj(υk)。设Gaiaj′是Gaiaj的一个连通子图。Kempe法色交换是在Gaiaj′中各点上的颜色ai、aj对调。由此可见,任一次Kempe法色交换都限定在一个连通两色子图中,且该子图中必须是所有点的颜色都要对调。因此,在某些情况时,用Kempe法色交换,由G的一种着色求另一种着色有可能实现不了。例1设最大平面图G已用χ(G)种颜色着色,如图1所示。χ(G)=4,将图G的着色分为A和B两种,当G为无结图时,G为A种着色。否则,G为B种着色。它们分别用图1(a)和图1(b)表示。在图1(a)所示的图G中,任一两色子图均是连通图。而在图1(b)所示的图G中,含有c、d两色交错回路(υ3,υ4,υ7,υ8,υ3),Gab是分离的,它含有2个连通子图。由此显见,仅用Kempe法色交换是无法将图G由A种着色改为B种着色,反之亦然。综上分析,A.B.Kempe运用Kempe法色交换来证明四色猜想,必然导致在某些情况下有可能使证明陷入无结果的循环状态。故Kempe的四色猜想证明缺乏严格性和周密性。2at色点交错出现的路径设图G用a1,a2,…,aχ(G)等χ(G)种颜色着色。若G中点υi和υj在两色子图Gasat(s,t=1,2,…,χ(G);s≠t)的同一连通子图中,则υi和υj之间至少存在一条as色点和at色点交错出现的路径,此路径名为υi和υj间asat两色交错路径,记为Pi,jasat。定理1设平面图G已用χ(G)种颜色着色,(υk,υl)是G中任一两色连通子图Ga1a2的一条割边,υk和υl分别着a1和a2色。令G′=G-(υk,υl),在G′的Ga1a2(υk)中各点颜色对调,不影响Ga1a2(υl)中各点着色,从而υk由a1改为a2色,而υl保持a2色。在G′中添加边(υk,υl),得图Gu。在Gu中υk和υl相邻且同为a2色,故Gu为非正常着色。若Gu中υk和υl之间存在χ(G)-1种两色交错路径,则其中至少有一种两色交错路径可被消除(变成非两色交错路径)。2.1模型a3l方法(1):设图Gu中υk和υl相邻且同为a2色,依据定理1,可从υk和υl之间χ(G)-1种两色交错路径中消除其中之一,不妨设被消除的两色交错路径为Pk,la2a3。令Gu′=Gu-(υk,υl),由于Gu′中已不存在Pk,la2a3,故在Ga2a3(υl)中各点颜色对调,不影响Ga2a3(υk)中各点着色。从而将υl由a2改为a3色,而υk保持a2色。在Gu′中添加边(υk,υl),恢复G的拓扑结构,此时G中υk和υl分别着a2和a3色,G为正常着色,且为一个新着色方案。方法(2):设Gu中υk和υl相邻且同为a2色。在Gu中包含υk或υl的另一种两色连通子图(不妨设它为Ga2a4)中作部分点的颜色对调,使相邻又同色的点对转移到Ga2a4中一条割边的两端点,不妨设它们分别为υf和υg,得到Gui。由定理1知,在Gui中υf和υg之间至少有1种两色交错路径不存在,令Gui′=Gui-(υf,υg)。此时可使Gui′中υf和υg成为异色,从而可使G获得1个新着色方案。上述方法(1)和方法(2)统称为转移法色交换。2.2转移法色交换与ga和b种Kempe法色交换须限定在一个连通两色子图中所有点的颜色对调,而转移法色交换没有这种限定条件,它允许在一个两色子图中仅作部分点的颜色对调,甚至仅将1个点的颜色由一种改着为另一种。它还允许相邻且同色点对由一种两色子图转移到另一种两色子图。显见转移法色交换是Kempe法色交换的延伸和发展,或者说Kempe法色交换只是在特定条件下的转移法色交换。两者相比,转移法色交换的交换范围灵活全面,作用深广,功能齐全,应用广泛。前面例1已指出,仅用Kempe法色交换是无法实现最大平面图G的A和B2种着色互相变换。然而,用转移法色交换可实现它们互相变换。(1)当图G由A种着色向B种着色转移时,转移过程如下:1)在图1(a)所示的G中将υ3和υ5的颜色互换,得Gu1。在Gu1中υ5和υ6相邻且同为c色,为非正常。2)在Gu1中将υ5和υ4的颜色对调,得Gu2,Gu2中υ4和υ6相邻且同为c色,为非正常。3)在Gu2中不存在P4,6cb。令Gu2′=Gu2-(υ4,υ6),在Gu2′的Gbc(υ6)中各点上的颜色b、c对调,υ6由c色改为b色,υ8由b色改为c色。在Gu2′中添加边(υ4,υ6),恢复G的原有拓扑结构,且得G的B种着色,如图1(b)所示。(2)当图G由B种着色向A种着色转移时,其转移过程是情况(1)的逆过程,不再赘述。3,3,4,5设平面图G中点υ0的邻点集为{υ1,υ2,υ3,υ4,υ5},令G′=G-υ0,并设G′可4-着色,在G′的一个着色方案中υ1,υ2,υ3,υ4,υ5分别着a,a,b,c,d色。为了便于叙述,将此着色方案的图G′简记为G0。定义1相干点对(υi·υj)。在G0中υi,υj(i,j=1,2,3,4,5;i≠j)着为异色,通过Kempe交换也不能着为同色,称υi和υj为相干点对,记为(υi·υj),这表示在υi和υj之间至少存在1条奇段数的两色交错路径。定义2不相干点对(υi;υj),在G0中υi,υj(i,j=1,2,3,4,5;i≠j)着为同色或通过kempe交换可着为同色,则υi和υj被称为不相干点对,记为(υi;υj),这表示υi和υj着同色后两者之间不存在奇段数的两色交错路径,但允许存在偶段数两色交错路径。在图G0中υ1,υ3,υ4,υ54个点以及它们之间的两色交错路径所构成的子图绝不是K4或K4的同胚图,否则该子图将与G中的υ0及其关联的边构成K5或K5的同胚图,由Kuratowski定理知,这与图G的平面性相矛盾。因此,在υ1,υ3,υ4,υ5中至少有1个不相干点对。同理,在υ2,υ3,υ4,υ5中也至少有1个不相干点对。由此可见,{υ1,υ2,υ3,υ4,υ5}中仅有1个同色点对υ1和υ2时,它中还至少有2个不相干点对,设为(υ1;υ3)和(υ2;υ4)。定义3X图和非X图。能同时满足下列5个条件的图G0称为X图。(1){υ1,υ2,υ3,υ4,υ5}中(υ1;υ2),(υ1;υ3)和(υ2;υ4)为不相干点对,且其中只有1个同色点对。{υ1,υ2,υ3,υ4,υ5}中其余各点对均为相干点对;(如图2所示,图中实线的两端点为相干点对,虚线的两端点为不相干点对)。(2)在Gab(υ1)中作kempe法色交换,υ2和υ4变成相干点对;(3)在Gab(υ3)中作kempe法色交换,υ2和υ4变成相干点对;(4)在Gac(υ2)中作kempe法色交换,υ1和υ3变成相干点对;(5)在Gac(υ4)中作kempe法色交换,υ1和υ3变成相干点对;否则,图G0被称为非X图。推论1当图G0为X图时,则G0中P3,5bd和P4,5cd间至少有1个d色公共中间点,并在该点它们互相交叉。为了强调图的着色方案,从此处本文将X图和非X图改称为G0的X和非X种着色,将G0的一着色方案为X或非X种着色简记为:G0为x或x¯x¯。引理1设简单平面图G有n个点,ne条边,各点次数均大于或等于5,则G中至少有12个次数为5的点。证明用反证法。设G中至多有11个次数5的点,其余各点次数大于等于6。那么由平面图必要条件知式(1)和式(2)相矛盾,故反证假设不成立。定理2设简单平面图G中各点次数大于等于5,υ0是G中任一次数为5的点,G的导出子图G0=G-υ0。若G0为x,则使用转移法色交换可将G0的着色方案由x变为x¯x¯。证明不妨设υ0的邻点在G0中构成回路C0,令C0=(υ1,υ5,υ2,υ3,υ4,υ1),将图G0嵌入一个平面,外区的周界为回路C0,并设G0用a,b,c,d等4种颜色着色,υ1,υ2,υ3,υ4,υ5分别着a,a,b,c,d色。因G0为x,故G0中必定存在(υ1;υ2),(υ1;υ3)和(υ2;υ4)等3个不相干点对,其中υ1和υ2是同为a色的点对。而且,G0中必定存在P3,5bd和P4,5cd,由推论1知它们至少有1个同为d色的公共中间点,并在该点它们相交叉。本文称该点是G0为x的交叉点。因G0中存在P3,5bd,故Gac(υ1,υ4)∩Gac(υ2)=∅,从而在Gac(υ1,υ4)中各点的颜色对调,不影响Gac(υ2)中各点着色,反之亦然。因G0中存在P4,5cd,故Gab(υ1)∩Gab(υ2,υ3)=∅,从而在Gab(υ1)中各点的颜色对调,不影响Gab(υ2,υ3)中各点着色,反之亦然。不失一般性,设G0中存在P3,5bd和P4,5cd各一条,令P3,5bd=(υ3,…,υj,υk,υf,…,υ5),P4,5cd=(υ4,…,υs,υk,υt,…,υ5)。显见υk为d色,且它是G0为x的交叉点,依据推论1和引理1,不妨设υk的次数为5。令G0′=G0-(υj,υk),故在G0′的Gbd(υj)中各点的颜色对调,不影响Gbd(υk)中各点着色。从而υ3,υj均由b色改为d色,不影响υk和υ5着色,υk和υ5均保持d色。在G0′中添加边(υj,υk),得Gou1。在Gou1中υj和υk相邻且同为d色,故Gou1是非正常着色。但Gou1中(P3,jbd+(υj,υk)+Pk,5bd)是一条由b、d两色组成的路径,简记为P3,5bd′。故在Gou1的Gac(υ1,υ4)中各点的颜色对调,不影响Gac(υ2)中各点着色,反之亦然。从而Gou1有如下情况。为了论述简洁,先作如下约定:令Goui′=Goui-(υj,υk),当Goui′中υj和υk变成异色点对时,在Goui′中添加边(υj,υk),恢复G0的拓扑结构,此时G0为正常着色。(1)Gou1中Pj,kda和Pj,kdc两者之一不存在。①设Pj,kda不存在。在Gou1中(υ3,υ2,υ5,υ1)是一条d,a两色交错路径。(A)若Gou1′不存在Pk,5da,那么在Gou1′的Gda(υk)中各点的颜色对调,υk由d色改为a色,υ3,υ2,υ5,υ1以及υj各点着色都不受影响,它们都保持原有的着色。此时,G0中υ1和υ2同为a色,υ3和υ5同为d色,故G0为x¯x¯。(B)若Gou1′存在Pk,5da,那么在Gou1′的Gda(υk)中各点的颜色对调,υk,υ3,υ2,υ5和υ1分别由d、d、a、d、a色改着为a、a、d、a、d色,但υj不受影响,它保持d色。此时,G0中υ1和υ2同为d色,υ3和υ5同为a色,故G0为x¯x¯。②设Pj,kdc不存在。在Gou1中υ3和υ4相邻,且它们分别着d和c色。(A)若在Gou1′中不存在Pk,5dc,那么Gdc(υk)中不含有υ5。(a)若Gdc(υk)中不含有υ3和υ4,那么在Gdc(υk)中各点的颜色对调,υk由d色改为c色,不影响υj,υ5,υ3和υ4各点着色,它们分别保持d、d、d和c色。因此,G0中υ1和υ2同为a色,υ3和υ5同为d色,故G0为x¯x¯。(b)若Gdc(υk)中含有υ3和υ4,那么在Gdc(υk)中各点的颜色对调,υk,υ3和υ4分别由d、d和c色改为c、c和d色,但不影响υj和υ5着色,υj和υ5保持d色。此时,G0中υ1和υ2同为a色,υ4和υ5同为d色,故G0为x¯x¯。(B)若在Gou1′中存在Pk,5dc,那么Gdc(υk)中含有υ5。(a)若Gdc(υk)中不含有υ3和υ4,那么在Gdc(υk)中各点的颜色对调,υk和υ5都由d色改为c色,υ3和υ4着色不受影响,它们分别保持d和c色。此时,G0中υ1和υ2同为a色,υ4和υ5同为c色,故G0为x¯x¯。(b)若Gdc(υk)中含有υ3和υ4,那么在Gdc(υk)中各点的颜色对调,υk,υ5,υ3和υ4分别由d,d,d和c色改为c,c,c和d色,但υj着色不受影响,它保持d色。此时,G0中υ1和υ2同为a色,υ3和υ5同为c色,故G0为x¯x¯。(2)Gou1中Pj,kda和Pj,kdc均存在。不失一般性,设υk的邻点构成回路Ck=(υj,υm,υs,υf,υt,υj)。显见Gou1中υj,υm,υs,υf,υt分别着d,a,c,b,c色。依据定理1可消除Pj,kda和Pj,kdc两者之一。①将Pj,kda消除。(A)若在Gou1中存在d、c两色回路C1=(υj,…,υ4,…,υs,υk,υj),则在回路C1内侧a色点和b色点上作颜色对调,将υm由a色改为b色,不仅消除了Pj,kda,而且不影响回路C0上各点着色,得Gou2。在Gou2中不存在Pj,kda,且υ1,υ5,υ2,υ3,υ4分别着a,d,a,d,c色。可见Gou2情况与Gou1的情况(1)①类同,故它的变换结果同样是G0为x¯x¯。(B)若Gou1中不存在回路C1。从而Gou1中不存在Pj,kdc=(υj,…,υ4,…,υs,υk)。又因Gou1中存在P3,5bd′,故在Gou1的Gac(υ1,υ4)中各点颜色对调,将υ1,υ4,υs,υm分别由a,c,c,a色改为c,a,a,c色。既不产生Pj,kda=(υj,…,υ4,…,υs,υk),又不影响Gac(υ2)中各点着色,υ2,υt分别保持a和c色,得Gou2。在Gou2中不存在Pj,kda,且υ1,υ5,υ2,υ3,υ4分别着c,d,a,d,a色。此时Gou2情况和Gou1的情况(1)①类同。(a)若Gou2′中不存在Pk,5da,则G0中υ2和υ4同为a色,υ3和υ5同为d色,且为正常着色,故G0为x¯x¯。(b)若Gou2′中存在Pk,5da,则G0中υ2和υ4同为d色,υ3和υ5同为a色,且为正常着色,故G0为x¯x¯。②将Pj,kdc消除。在使C0上有2个a色点和2个d色点,或有2个c色点和2个d色点条件下,消除Pj,kdc和消除Pj,kda对G0为x¯x¯而言是等价的,其过程与情况(2)①类同,这里不再赘述。综上分析,所有可能的情况,转移法色交换可使G0的着色方案由x变换成x¯x¯。例2设平面图G0如图3所示。由于该图G0同时满足定义3中5个条件,故G0的着色方案为x。依据定理2,采用转移法色交换必然可使G0的着色方案由x变换成x¯x¯。其过程如下:(1)设G0′=G0-(υ10,υ14),在G0′的Gbd(υ14)中各点颜色对调,使υ14,υ3,υ23,υ21,υ17,υ19分别改染为b,d,b,d,b,d色。在G0′中添加边(υ10,υ14),恢复G0的拓扑结构,将它记为Gou1。在Gou1中υ10和υ14相邻且同为b色是非正常着色。(2)设Gou1′=Gou1-(υ10,υ14),由于在Gou1′的υ10和υ14之间不存在P10,14ab,故在Gou1′的Gab(υ14)中作Kempe交换,使υ14,υ16,υ17分别改染为a,b,a色。而υ10着色不受影响,它保持b色,在Gou1′中添加边(υ10,υ14),恢复图G0的拓扑结构,且为正常着色。图G0新的着色方案如表1所示。由此可见,当图G0为新着色方案时,{υ1,υ2,υ3,υ4,υ5}中含有2个同色点对,故此时图G0为x¯x¯。定理3若图G0为x¯x¯,则G0中υ1,υ2,υ3,υ4,υ5等5个点可3-着色。证明(1)当G0不满足定义3中条件(1)时。(A)设{υ1,υ2,υ3,υ4,υ5}中有4个以上不相干点对,不妨设有4个。除原有3个外,另设一个不相干点对为(υi;υj)。(a)当υi和υj之一为a色点时,不妨设它为(υ1;υ5)。因υ1和υ5为不相干点对,故不存在P1,5ad,从而也不存在偶段数的P1,2ad。那么,在Gad(υ1)中各点颜色对调,υ1改染为d色,υ2不受影响,保持a色。此时,若(υ3·υ1)和(υ3·υ5)两者之一存在,则υ2和υ4必为不相干点对。故在Gac(υ2)中各点颜色对调,υ2改染为c色,υ4不受影响,它保持c色。可见υ1,υ2,υ3,υ4,υ5分别着d,c,b,c,d色,故上述5个点可3-着色。反之,若存在(υ2·υ4),则(υ3·υ1)和(υ3·υ5)均不存在。故在Gbd(υ3)中各点颜色对调,υ3改染为d色,υ1和υ5都不受影响,都保持d色。可见υ1,υ2,υ3,υ4,υ5分别着d,a,d,c,d色,故上述5个点可3-着色。(b)当υi和υj均不为a色点时,不妨设它为(υ4;υ5)。那么,在Gcd(υ4)中各点颜色对调,υ4改染为d色,υ5不受影响,保持d色。此时υ1,υ2,υ3,υ4,υ5分别着a,a,b,d,d色,故上述5个点可3-着色。(B)当{υ1,υ2,υ3,υ4,υ5}中有2个以上同色点对时,显然上述5个点可3-着色。(2)当G0不满足定义3中条件(2),(3),(4)和(5)之一时。不妨设它不满足条件(2)时。已知υ4和υ5为相干点对,从而存在P4,5cd。那么,在Gab(υ1)中各点颜色对调,υ1改染为b色,υ2和υ3都不受影响,它们分别保持a色和b色。又由于在Gab(υ1)中各点颜色对调,υ2和υ4仍保持为不相干点对,从而在Gac(υ4)中各点颜色对调,υ4改染为a色,υ2不受影响,保持a色。此时υ1,υ2,υ3,υ4,υ5分别着b,a,b,a,d色,故上述5个点可3-着色。4转移法色交换定理4(四色定理)每一个平面图是可4-着色的。证明当平面图G不超过4个点时,定理显然成立。应用归纳法,假定平面图G中有n-1个点,定理成立。当G有n个点时。因为G是平面图,故G中至少有一个点的次数不大于5。不妨设d(υ0)≤5。导出子图G′=G-υ0,G′具有n-1个点,根据