论文部分内容阅读
图论是数学的一个重要分支,是一门发展迅速的新兴学科.染色理论是图论中十分活跃的研究课题,它的研究带动了整个图论的发展.图的染色理论有很多的分支,如边染色,点染色,全染色等.本文主要研究染色理论中边染色相关的一些问题. 本文主要做了以下工作: 首先说明了课题的研究背景和研究意义,接着对涉及到的相关概念及符号进行介绍.本文的证明内容分为两部分.第一部分是对V iz in g提出的临界图猜想进行研究.主要用Discharge方法和临界图的相关性质对猜想的结果予以改进,分别给出了7-临界图、不含5-点的8-临界图、9-临界图的边数的新下界.第二部分是对V iz in g定理的研究. V iz in g首先证明:若 G是简单平面图,当最大度为2,3,4,5时,G可能为第一类图,也可能为第二类图;当最大度至少为8时,G是一定第一类图.并且猜想当最大度为6,7时,G是第一类图. Sanders和Zhao及 Zhang分别在2000年和2001年证明了最大度为7的简单平面图为第一类图.目前为止,仅有最大度为6的情形未得到证明.本文提出了最大度为6的简单平面图是第一类图的一个充分条件,对后续的研究具有一定的意义.