资源描述：
《现代图论课程论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、浙江师范大学研究生课程论文封可平面图的非正常染色摘要：本文介绍丫可平面图的非正常染色的研允背景和现状，并以《不含4-圈和6-圈的可平面图是(2,0,0)-可染的》这篇文章为例，研究了无4_,5-圈的可平面图的(1,0,0)-可染的一些成果。最后，简述了本学期学习现代图论这门课程的心得体会。关键词：非正常可染；研究竹景和现状；方法和技巧；心得体会1课题背景染色理论是图论的重耍内容，也是图论的起源之一。图的染色问题的研究来源于著名的四色问题，•有重要的理论依据和实际意义。而的非正常染色是图的正常染色的一个延伸。一个有序对G=(V，£)称为无向图，其中V
2、表示一个有限集合，£是7中不同元素的无序对组成的集合。V中的元素叫做G的顶点，£中的元素叫做G的边。通常用V，£分别表示G的顶点集与边集。若一条边的始点和终点是同一个顶点，则把这样的边称为环。若两条以上的边的一对端点相同，则把这些边称为重边。把没有重边和环的图称为简单图。如果可以把图G画在平而上，使得它的边仅在端点处相交，则称图G为可平面图.把可平面图在平面内具体的使得边仅在端点处相交的嵌入叫做平面图。我们所研究的3-可染图形都是有限的，简单的，无向的图形。通常用w,v表示G屮的点，e表示G屮的边.若6=卯€V(G),则称w和v在G中相邻，或称w和
3、v互为邻点，或又称《和v是e的两个端点，或称w和v都与v相关联。与v相关联的边的条数叫做v的度数，记作J(v)。^d(v)=k^d{v}>k,或则称v为一个/：-点(或r-点，或zr-点)，对/类似定义令c是g的一个圈，/价(C)和£x“C)分别表示由(严格)位于c的内部或者外部的点构成的G的一个生成子图。特别地，Int(C)=GExt(C)fExt(C)=GInt(C)o若Int(C)本中*£xr(C)(EPG至少有一个的点在C的内部和外部)，称C是分离圈。连接C上两个不相继的点的边称为C的弦。若弦e关联一个三角形称e是三角的。令«，……久为
4、k个非负整数。若我们能用1，2,......彳这々种颜色来染G=(V,E)中的顶点使得点导出子图OfV；」具有最大度式，其中是颜色为Z的顶点集，/=1,2,……人则称G是非正常(dpd2,……，么)-可染的，简称(d,,d2,，dAJ-可染的。坏圈由一个3,3,6,6剖分构成的8圈和四个9圈构成，其中四个9圈分别是3,3,6,7剖分，3,6,6剖分，3,6,6,6剖分和一个3,6,3,6,3,6剖分。好圈是9-非坏的圈。2可平面图的正常3-染色的研究现状2.1著名的猜想及已知结果四色猜想：可平面图都是4-可染的.见[1][2].Grotzsch三色
5、定理：不含3-圈的可平面閔是3-可染的.见[3].Steinberg猜想：不含4-圈和5-圈的可平面图是3-可染的.见[4].猜想：两个三角形的距离6/v足够大的可平面图是3可染.见[5].以下是较Steinberg猜想更弱的Bordeaux猜想Bordeaux猜想:含相邻三角形及5-(1)不含相交三角形及5-圈的可平面图是3-可染的.(2)不E的可平面图是3-可染的.针对猜想，•提出一个问题：是否存在一个最小值/:，使得每一个不含4-至圈的平面图是3-可染的。围绕这个问题，O.V.Borodin,H.L.Abbott,A.TV.G/etov等人进
6、行了很多深入的研究，得到以下一些结果：B11,见[7].k< f见[8].B9,见[9].々S7,见[10].关于可平面图的3-可染，Y.Wang,W.Wang,M.Chen,等人给出以下一些充分条件：[11]-[15].不含4-，5-,不含4-，6-,不含4-，6-,不含4-，6-,不含4-，7-,不含4-，/-，j-，A-圈的可平面图是3-可染的，其中.见7-圈的平面图是3-可染的.见[16].7-圈的平面图是3-可染的.见[17].8-圈的平面阁是3-可染的.见[18].9-圈的平面图是3-可染的.见[19].9-圈的平面图是3-可染的.见
7、[20].至今尚无人能证明出平面图不含4-至6-圈是否是(0,0,0)_可染的。对于平面阁的非正常染色，如下列出部分著名结果。每个平面图是(2,2,2)_可染的。见[6]每个平面图是(3,2)、可染的。见[21][22]。不含3-圈的平面阁是(3，1)*_可染的。见[23]不含相邻三角形和5-圈的平面图是(1，1，1)-可染的。见^4]不含4-圈和5-圈的平面图是可染的。见t25]对于平面图不含4-圈和;-圈，f关5我们又有以卜结果"既不含4-圈又不含6-圈的平面图是(3,0,0)-(1，1，0)-可染的。见[26]既不含4-圈又不含6-圈的平而图
8、是(2,0,0)_可染的。见对于平面图不含4至6-圈的平面图是否是(0,0,0)_可染的，暂无人证明。不含4至6-圈的平面
