现代图论课程论文.docVIP

浙江师范大学 研究生课程论文封面 可平面图的非正常染色 摘要：本文介绍了可平面图的非正常染色的研究背景和现状，并以《不含4-圈和6-圈的可平面图是(2,0,0)-可染的》这篇文章为例，研究了无4-，5-圈的可平面图的(1,0,0)-可染的一些成果。最后，简述了本学期学习现代图论这门课程的心得体会。 关键词：非正常可染；研究背景和现状；方法和技巧；心得体会 1 课题背景 染色理论是图论的重要内容，也是图论的起源之一。图的染色问题的研究来源于著名的四色问题，具有重要的理论依据和实际意义。而的非正常染色是图的正常染色的一个延伸。 一个有序对称为无向图，其中表示一个有限集合，是中不同元素的无序对组成的集合。中的元素叫做的顶点，中的元素叫做的边。通常用,分别表示的顶点集与边集。若一条边的始点和终点是同一个顶点, 则把这样的边称为环。 若两条以上的边的一对端点相同,则把这些边称为重边。把没有重边和环的图称为简单图。 如果可以把图画在平面上, 使得它的边仅在端点处相交, 则称图为可平面图. 把可平面图在平面内具体的使得边仅在端点处相交的嵌入叫做平面图。我们所研究的3-可染图形都是有限的,简单的，无向的图形。 通常用,表示中的点, 表示中的边. 若,则称和在中相邻, 或称和互为邻点, 或又称和是的两个端点, 或称和都与相关联。与相关联的边的条数叫做的度数，记作。若(或, 或),则称为一个-点(或点, 或点)，对类似定义令是的一个圈，和分别表示由(严格)位于的内部或者外部的点构成的的一个生成子图。特别地，,。若(即至少有一个的点在的内部和外部)，称是分离圈。连接上两个不相继的点的边称为的弦。若弦关联一个三角形称是三角的。 令为k个非负整数。若我们能用1,2,……,这种颜色来染中的顶点使得点导出子图具有最大度，其中是颜色为的顶点集，,则称G是非正常-可染的，简称-可染的。坏圈由一个3,3,6,6剖分构成的8圈和四个9圈构成，其中四个9圈分别是3,3,6,7剖分，3,6,6剖分，3,6,6,6剖分和一个3,6,3,6,3,6剖分。好圈是非坏的圈。 2 可平面图的正常3-染色的研究现状 2.1著名的猜想及已知结果 四色猜想：可平面图都是4-可染的.见[1][2]. 三色定理：不含3-圈的可平面图是3-可染的.见[3]. 猜想：不含4-圈和5-圈的可平面图是3-可染的.见[4]. 猜想：两个三角形的距离足够大的可平面图是3可染.见[5]. 以下是较猜想更弱的猜想 猜想：（1）不含相交三角形及5-圈的可平面图是3-可染的.(2)不含相邻三角形及5-圈的可平面图是3-可染的. 针对猜想,提出一个问题：是否存在一个最小值，使得每一个不含4-至-圈的平面图是3-可染的。 围绕这个问题，,,等人进行了很多深入的研究，得到以下一些结果： ,见[7]. ,见[8]. ,见[9]. ,见[10]. 关于可平面图的3-可染，Y.Wang,W.Wang,M.Chen,等人给出以下一些充分条件： 不含4-,,,圈的可平面图是3-可染的，其中.见 [11]-[15]. 不含4-, 5-, 7-圈的平面图是3-可染的.见[16]. 不含4-, 6-, 7-圈的平面图是3-可染的.见[17]. 不含4-, 6-, 8-圈的平面图是3-可染的.见[18]. 不含4-, 6-, 9-圈的平面图是3-可染的.见[19]. 不含4-, 7-, 9-圈的平面图是3-可染的.见[20]. 至今尚无人能证明出平面图不含4-至6-圈是否是-可染的。对于平面图的非正常染色，如下列出部分著名结果。 每个平面图是-可染的。见 每个平面图是-可染的。见。 不含3-圈的平面图是-可染的。见 不含相邻三角形和5-圈的平面图是-可染的。见 不含4-圈和5-圈的平面图是-可染的。见 对于平面图不含4-圈和圈，我们又有以下结果。 既不含4-圈又不含6-圈的平面图是--可染的。见 既不含4-圈又不含6-圈的平面图是-可染的。见 对于平面图不含4至6-圈的平面图是否是-可染的，暂无人证明。 不含4至6-圈的平面图是否是（1,0,0）-可染的。见 2.2 可研究课题 在证明了每个平面图是-可选的后，Eaton,Hull等人提出：每个平面图是否是-可选的？我们在此提出每个平面图是否是-可染的，若不是，那是否是-可染的？无4-圈和圈的平面图是否是(1,0,0)-可染的？无4-圈和圈的平面图是否是(0,0,0)-可染的？ 3 方法与技巧 该部分以《不含4-圈和5-圈的平面图是(1,0,0)-可染的》为例，介绍了图的点荫度方法与技巧。本文定理：不含4-圈和5-圈的平面图是(1,0,0)-可染的。该定理的证明是通过反证法来证明的。设是定理3关于点数最少的一个极小反例，即是不含4-圈和5-圈，它本身不是(1,0,0)-可染的，但