1-平面图的无圈边染色数

来源 :河南大学 | 被引量 : 0次 | 上传用户:treef620
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图G的无圈k-边染色是指图G的一个正常边染色且不产生双色圈的k-边染色.图G的无圈边染色数χa’(G)是使得图G有一个无圈k-边染色的最小整数k.在1978年,Fiamcik提出了任意图的无圈边染色数不超过△(G)+ 2的猜想,△(G)表示图G的最大度.在2001年,Alon等人又一次在文献中陈述了这个猜想.研究者们称这个猜想为"无圈边染色猜想",简记为"AECC".图G是k-闭极小图,是指最大度不超过k的图G,其任意真子图H都满足χa’(G)>且χa’(H)≤k.图G是1-平面图,是指它可以画在平面上使得每一条边至多与一条其他的边相交.图G是平面图,是指它可以画在平面上使得每一条边都不与其他的边相交.很明显平面图符合1-平面图的定义,即平面图都是1-平面图.本论文共证明了两个结论,一个是不含三角形的1-平面图G,无圈边染色数χa’(G)≤A(G)+ 14.另一个是满足围长至少为5的1-平面图G,无圈边染色数χa’(G)≤△(G)+7.论文内容共分为五章.第一章是引言,介绍图论的起源,图论起源于非常经典的哥尼斯堡七桥问题.介绍图论的历史发展,图的染色问题的意义,图的无圈边染色相关概念的产生,并对论文的主要内容进行简要介绍.第二章是基础知识,阐述全文将要用到的一些基本概念和符号,以及一些关于图的无圈边染色数的研究成果.按照研究对象分为围长比较大的图,正则图,最大平均度比较小的图,最大度比较小的图,1-平面图,平面图,围长比较大的平面图,不含短圈相互关联的平面图,不含短圈的平面图,外平面图这些类进行介绍.第三章是一些结构引理,主要是为后面两章的证明做准备.第四章是要证明的第一个结果,在已有1-平面图无圈边染色数结论的基础上,结合已知的结构引理,改进了Wang等人证明的结果,即不含三角形的1-平面图的无圈边染色数不超过△+ 17,本篇文章用权转移方法证明了不含三角形的1-平面图的无圈边染色数不超过△ + 14.第五章是要证明的第二个结果,通过添加围长条件并结合已知的结构引理,证明了围长至少为5的1-平面图的无圈边染色数上界为△ + 7.
其他文献
生态学有很多的组成部分,但其中最重要的一个组成部分是种群生态学。种群生态学也是数学在生态学中,迄今为止运用最为广泛与深入的,且发展最为系统和成熟的部分,从而种群动力
空泡率是两相流研究领域重要流动参数,其测量准确程度将直接影响到两相流体其它参数的测量精度。电容法是利用气液介电常数的不同来测量两相流动空泡率的方法,具有结构简单,
20世纪20年代,著名芬兰数学家R.Nevanlinna系统运用Possion-Jensen公式,创立了亚纯函数值分布理论,堪称二十世纪最伟大的数学成就之一。它不仅奠定了现代亚纯函数的理论基础,
随着现代客运行业的发展与人们生活水平的不断提升,人们出行的次数越来越多。并且人们出行的时候有时会与他人结伴同行或是一起组团出行,比如与人一起出差、与好朋友一起旅游
采用吸热型碳氢燃料作为冷却剂的再生冷却可以有效地解决超燃冲压发动机的热防护问题。通常用于流量测量的差压式流量计和用于壁面冷却的冷却通道是再生冷却系统的重要组成部
偏微分方程理论可以被应用在许多科学领域,例如生物学,物理学,化学,工程学,控制理论,人口增长模型和气候模型。在过去几年,带有偏差变元的偏微分方程的基础理论的研究得到了
设S是序幺半群.文献[14]中证明了所有强平坦的序左S-系是I-正则的当且仅当S是左PP且左半完全的序幺半群.本文第一部分证明了上述结论中的左半完全性可被更弱的性质(FP2)代替或
研究多维分布时需要考虑其相关性问题,用Copula函数来描述变量间的相关结构,不需要每次计算相同的边缘分布,且任意边缘分布都可以通过Copula函数构造联合分布。因此,许多国内
恢复和保育生态系统服务功能既是人类生存和现代文明的基础,也是实现可持续发展的前提。研究与探讨喀斯特石漠化地区不同土地覆被对生态系统服务功能的影响机制,可为我国西南
图G=(V,E)的边着色是一个映射c:E(G)→S,使得任意两条相邻的边e和f,满足c(e)≠ c(f).图的强边着色是图的边着色并且要求在图中和同一边相邻的两条边也要着不同的颜色.换而言之,在强边