论文部分内容阅读
平面图G的无圈κ-边着色是指图G的一个正常的不产生双色圈的κ-边着色.G的无圈边着色指数Xa(G)为使得G有一个无圈κ-边着色的最小的整数κ.Alon等.第一个提出了关于无圈边着色指数的一般线性关系.它可以作为参数用来界定一些其它着色指数.例如:星着色指数.本学位论文主要是想通过进一步研究平面图的结构,进而改进平面图无圈边着色指数的界. 全文内容分为四章. 第一章介绍无圈边着色相关概念的产生,及最新研究的结果,并且对论文的主要内容及论文的结构进行简要介绍. 第二章阐述全文将要用到的一些基本事实,并列出无圈边着色和无圈边着色指数的相关概念. 第三章是论文的一个重要内容.在已有无圈边着色指数结论的基础之上,结合一些主要研究结果及方法给出了4-,5-,3-,10-点的改进结构. 第四章是在第三章的基础上和一些已知的结论,利用权转移的方法改进了平面图的无圈边着色的界.