1-平面图的无圈边

来源 :河南大学 | 被引量 : 0次 | 上传用户:saoluan
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图 G的无圈fc-边染色是指图G的一个正常边染色且不产生双色圈的fc-边染色.图G的无圈边染色数x U G)是使得图G有一个无圈fc-边染色的最小整数k.在1978年, Fiamcik提出了任意图的无圈边染色数不超过A(G)+2的猜想,A(G)表示图G的最大度.在2001年,Alon等人又一次在文献中陈述了这个猜想.研宄者们称这个猜想为“无圈边染色猜想”,简记为“AECC”.图G是k-闭极小图,是指最大度不超过k的图G,其任意真子图H都满足xUG)> k且xJH)< k.图G是1-平面图,是指它可以画在平面上使得每一条边至多与一条其他的边相交.图G是平面图,是指它可以画在平面上使得每一条边都不与其他的边相交.很明显平面图符合1-平面图的定义,即平面图都是1-平面图.  本论文共证明了两个结论,一个是不含三角形的1-平面图G,无圈边染色数xl(G)< A(G)+14.另一个是满足围长至少为5的1-平面图G,无圈边染色数xl(G)< A(G)+7.  第一章是引言,介绍图论的起源,图论起源于非常经典的哥尼斯堡七桥问题.介绍图论的历史发展,图的染色问题的意义,图的无圈边染色相关概念的产生,并对论文的主要内容进行简要介绍.  第二章是基础知识,阐述全文将要用到的一些基本概念和符号,以及一些关于图的无圈边染色数的研宄成果.按照研宄对象分为围长比较大的图,正则图,最大平均度比较小的图,最大度比较小的图,1-平面图,平面图,围长比较大的平面图,不含短圈相互关联的平面图,不含短圈的平面图,外平面图这些类进行介绍.  第三章是一些结构引理,主要是为后面两章的证明做准备.  第四章是要证明的第一个结果,在已有1-平面图无圈边染色数结论的基础上,结合已知的结构引理,改进了W ang等人证明的结果,即不含三角形的1-平面图的无圈边染色数不超过A+17,本篇文章用权转移方法证明了不含三角形的1-平面图的无圈边染色数不超过A+14.  第五章是要证明的第二个结果,通过添加围长条件并结合已知的结构引理,证明了围长至少为5的1-平面图的无圈边染色数上界为A+7.
其他文献
学位
本文基于Yom osa提出的平面基转子模型通过对碱基的角转动位移来研宄D N A双螺旋链的非线性动力学问题.对碱基对在垂直于螺旋轴平面绕双螺旋链转动的角?和进行讨论.在数值实
学位
本文主要研宄一类非阿贝尔涡旋方程组解的存在性及其应用,分别建立了这类方程组在一个双周期区域和全平面上涡旋解的存在唯一性定理.在双周期区域上,分别采用直接极小化方法和
Clifford分析作为单复变函数理论在高维空间的一种推广,研究的是从实变量空间映射到不可交换的实Clifford代数的函数理论,它有非常重要的理论意义和应用价值.例如在Maxwell方程
本文给出了一类非线性、随机与役龄相关投资系统模型.研究了非线性与役龄相关投资系统解的存在性、唯一性,非线性与役龄相关投资系统的动态最优反馈控制及随机与役龄相关投资
在二十世纪后半叶,利用小波变换对不同维数的信号和图像等进行分析已经成为一种很重要的方法.然而小波变换方向选择性少,在表示图像的直线或者曲线奇异性结构时,并不是最优的