资源描述：
《a_q_类平面图及其可4_着色的证明》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1996年3月北京邮电大学学报Mar.1996第19卷第1期JournalofBeijingUniversityofPostsandTelecommunicationsVol.19No.1A(Q)类平面图及其可4-着色的证明徐志才(北京邮电大学应用科学技术系,北京100088)摘要首先提出Q图概念,将平面图分为A(Q)和B(Q)两类,然后证明了A(Q)类平面图可42着色.关键词平面图;着色;准色交错路径;Q图;A(Q)类平面图分类号O15715b1840年,数学家茂比乌斯(Mobius)提出了对任一平面地图用4种颜色可使任意相邻两国着不同色的猜想.1969年
2、奥尔(Ore)和斯坦普尔(Stemple)证明了所有直到有39个点的平面图都是可42着色的.1976年夏,美国数学家阿培尔(K.Appel)和黑肯(W.Haken)依靠计算机的帮助证明了四色猜想为真.但至今尚未见过四色猜想的理论证明.本文将平面图分为A(Q)和B(Q)两类,并从理论上证明任一A(Q)类平面图均可42着色.1定义设平面图G中点v0的邻点集为{v1,v2,v3,v4,v5},令G′=G-v0,并设G′可42着色.[1]在G′中至少有3个不相干点对,并在文献[1]中将G′称为图G0.定义1Q图.设图G0中v1,v2,v3,v4,v5分别着a,a,b
3、,c,d色,并设由v1和v2以及{v3,v4,v5}中任意两点构成的集合为Vs(即Vs={v1,v2,v3,v4},或Vs={v1,v2,v3,v5},或Vs={v1,v2,v4,v5}),若图G0满足下列条件之一,则G0被称为Q图.1)在Vs中[1]有3个不相干点对,且至多有3种准色交错路径.2)在Vs中有4个不相干点对.3)在{v1,v2,v3,v4,v5}中有大于等于5个不相干点对.定理2A(Q)类平面图和B(Q)类平面图.设平面图中点v0的次数等于5,导出子图G′=G-v0.若G′为Q图,则G被称为A(Q)类平面图.否则,G为B(Q)类平面图.2定理
4、与证明定理1若图G0为Q图,则G0中v1,v2,v3,v4,v5等5个点可32着色.证明(1)在Vs中有3个不相干点对,且至多有3种准色交错路径时.不妨设Vs={v1,v2,v3,v4},Vs中3个不相干点对分别是(v1;v2),(v1;v3)和(v2;v4).由于在v1和v3间以及v2和v4间总共可有4种准色交错路径.但根据假设至多有3种准色交错路径.故G0中至少有收稿日期:1995203210©1994-2010ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://w
5、ww.cnki.net92北京邮电大学学报19961一种准色交错路径不存在.不妨设P不存在.因为在G0中v1,v2,v3,v4,v5分别着a,a,b,c,d色,且(v1;v3)为不相干点对,故[1]在G0的衍生图G1=G0(Gab(v1))中v1,v2,v3,v4,v5分别着b,a,b,c,d色.上式中Gab[1]1(v1)表示包含点v1的a,b两色子图.由文献[1]知,P=P2,4(acbc,b∈Gab(v1),a
6、Gab(v1)).1[2]G0中不存在P,故用Kempe法在G0的Gab(v1)中色交换不会导致出现P2,4ac两色交错[1]路径.因此,在G
7、1中用v2和v4仍为不相干点对,在G1的Gac(v2)中色交换可使v2由a色改为c色,而v4仍保持c色.显然在G1的衍生图G1(Gab(v1))中v1,v2,v3,v4,v5,分别着b,c,b,c,d色.由此可见,G0中v1,v2,v3,v4,v5等5个点可32着色.(2)在Vs中有4个不相干点对时.不妨设Vs={v1,v2,v3,v4}.(a)若在Vs中有一个不相干点对为(v3;v4),由于v3和v4分别着b色和c色,都不是a色,故在G0的Gbc(v3)或Gbc(v4)中色交换可使v3和v4同为c色或同为b色.从而可使v1,v2,v3,v4,v5的着色由用
8、4种颜色降为用3种颜色.(b)若Vs中v3和v4为相干点对.不失一般性,设Vs中4个不相干点对分别为(v1;v2),(v1;v3),(v2;v4)和(v1;v4).由此可见v1,v2,v4都互不相干,它们可为同色.若它们同为a色,那末G0中v1,v2,v3,v4,v5分别着a,a,b,a,d色,即上述5个点可32着色.(3)在{v1,v2,v3,v4,v5}中有大于等于5个不相干点对时.不失一般性,设{v1,v2,v3,v4,v5}中有5个不相干点对.(a)若{v1,v2,v3,v4,v5}中有一个不相干点对(v3;v4),或(v3;v5),或(v4;v5)
9、.由于它们有如下共同特点:不相干的两点为异色,且都不
