图的强边染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:wuxin0226
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文考虑的图均为有限简单图.给定一个图G,我们将G的顶点集、边集、最大度、最小度、最大平均度及边e,e间的距离分别记作V(G),E(G),△(G),δ(G),mad(G)和dG(e,e).  若图G存在一个同构图G,其中G的顶点均在同一个平面内,而G的边只能在端点处相交,则称G为平面图.在平面图G中,用F(G)来表示G的面集.  设映射ψ:E(G)→{1,2,…,k}.若e,e∈E的距离至多为2,有ψ(e)≠ψ(e),则称ψ是G的一个强k-边染色.若G有一个强k-边染色,则称图G是强k-边可染的,且把xs(G)=min{k|G有一个强k-边染色}称为G的强边色数.  对于图的强边色数,1989年,Erd(o)s和Ne(s)etril提出了关于其上界的一个著名的猜想.设图G的最大度为△,则(1)若△为偶数,则xs(G)≤5/4△2;(2)若△为奇数,则xs(G)≤1/4(5△2-2△+1).对于这个猜想,学者们做了大量的研究工作,得出了很多重要的结果.  本文在已有的研究基础上,主要研究了不含部分短圈的平面图的强边色数及限制图的最大平均度时的强边色数,共分为四个章节.本文的第一章主要介绍了一些相关的概念,并对强边染色的研究现状和可研究的问题做了概括.第二章主要研究了围长大于等于7的平面图以及围长大于等于5的平面图的强边染色.第三章主要讨论了△(G)=4的图的强边染色,在分别给图G的最大平均度一个限制条件下,得出了G的强边色数的上界.第四章证明了不含若干短圈的△(G)=4的平面图,其强边色数的上界为19.
其他文献
医院教学实践在医学教学中有着举足轻重的地位,所以,对医院教学管理模式的研究与探讨十分重要.本文结合当前医院教学实际情况,首先介绍了现在医院教学中存在的一些问题,然后
对于经典的复合泊松模型,已经有着很多论述,并且有很多丰富的结果。本文在经典的复合泊松模型的基础上考虑了破产时间间隔和下一时刻的索赔额之间存在某种相依性结构的复合泊松
年赛
期刊
机器证明理论是数学中尤其是组合数学中一个重要的分支,它利用计算机来证明一些人工很难证明的恒等式,而证明恒等式的成立也是基于一些漂亮的算法和方法,其中WZ方法是最为广泛使
学位
张量可以看成是高维矩阵,和矩阵有着类似的性质和处理方法,类比矩阵分解,本文介绍了两种重要的张量分解方法,其中CANDECOMP/PARAFAC分解将张量分解为秩一张量加和的形式,可以看成
本篇硕士论文主要研究了从最小M(o)bius不变空间B1到Bloch空间上的Volterra复合算子的有界性和紧性的问题.我们分别给出算子Ig,ψ:B1→B和算子Vg,ψ:B1→B的有界性和紧性的充分
网络纠错的目标是将已有的针对点对点通信的经典纠错编码理论中的结果推广到复杂且规模较大的网络通信背景中。现有的关于网络纠错编码的结果大多只针对无圈网络。然而,在实际
江上舟,小小少年,却已经举办过两次个人画展,出版过两部个人作品集。他的画所表现出的审美观与想象力,充满着天真与童趣,开放思维、大胆创新、灵气逼人的画风,也透视出不凡的