图的强边染色问题研究

发布时间：2020-03-21 14:20

【摘要】：1736年,瑞士数学家Euler在他的论文中讨论了哥尼斯堡七桥问题,由此诞生了一个全新的数学分支-图论。自从四色猜想被提出之后,图的染色问题就成为了图论的一个很重要的研究课题。图的染色理论在计算机理论、组合最优化、信息化科学和网络设计等方面均有着很重要的应用。图的染色理论有很多分支,如边染色、点染色、面染色和全染色等。其中研究最多,结果也较完善的就是图的边染色。本文旨在讨论图的一种比较特殊的边染色-强边染色。本文主要由五个章节组成,主要内容如下:在第一章,我们首先给出本文用到的基本概念和记号,接着介绍图的强边染色的研究背景和研究现状,最后给出了本文的主要结果。在第二章,我们着重研究稀疏图的强边染色问题。Hocquard等人最早是研究了最大度小于或等于3(Subcubic graphs)的稀疏图的强边染色。最近,Bensmail等人研究了最大度为4的稀疏图的强边染色,他们证明了最大度为4并且最大平均度分别小于16/5,10/3,17/5,18/5,19/5的图分别可以用16,17,18,19,20种颜色来强边染色。我们改进了他们的结果,证明了最大度为4并且最大平均度分别小于61/18,7/2,18/5,15/4,51/13的图分别可以用16,17,18,19,20种颜色来强边染色。在这一章的第二部分,我们证明了最大度为4并且最大平均度分别小于8/3,14/5的图分别可以用10,11种颜色来强边染色,并且给出两个图说明这两个最大平均度是接近最优的。在第三章,我们证明了最大度为△(△≥6)并且最大平均度小于14/5的图可以用3△-1种颜色来强边染色。作为这一结果的一个结论,我们得到最大度为△(△ ≥ 6)并且围长g ≥ 7的平面图可以用3△-1种颜色来强边染色,从而改进了Wang的结果:所有最大度为△ ≥ 6并且围长g7的平面图可以用3△种颜色来强边染色。在第四章,我们首先集中精力研究伪Halin图的强边染色问题。伪Halin图是Halin图的一般推广。对Halin图的强边染色的研究,最早是Shiu等人,他们证明了Cubic Halin图强边色数至多是9。最近,Hu等人给出了Halin图的强边染色数的一个上界:每个△≥4的Halin图的强边染色数最多是2△+1。这一章我们证明了:每个△ ≥ 4的伪Halin图的强边色数最多是3△-2。需要说明的是,这个上界是接近最好可能的界,因为我们找到一个伪Halin图,它的强边色数刚好等于3△-3。在这一章的最后,我们将主要探讨K2,3-minor free图的强边色数问题。我们将证明:每个非空K2,3-minorfree图的强边色数最多是4△-6,并且得到这个界是最好的,因为存在一个非空K2.3-minor free图的强边色数刚好为4△-6。第五章作为本文的结束部分,我们提出了可以进一步考虑的研究问题。
【学位授予单位】：华中师范大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 晏伟峰;曹宇淇;;一道高考染色问题的创新解法及推广[J];中学数学研究;2019年04期

2 拉毛草;;“无心”和“有心”染色问题[J];数学学习与研究;2015年11期

3 黄玉娇;;对一类环形染色问题的探究[J];中学数学研究;2017年02期

4 郭文欣;;从染色问题谈两个计数原理的教学[J];中学数学;2008年21期

5 任丹丹;;一道染色问题的妙解[J];上海中学数学;2008年01期

6 刘海龙;;染色问题的相互转换探究[J];福建中学数学;2009年05期

7 王跃进;牛伟强;;关于2×n方格的染色问题研究[J];中学数学研究;2011年01期

8 卢建立;任凤霞;;3×n方格染色问题的两个新结果[J];数学通报;2011年12期

9 魏跃兵;一类染色问题的解法[J];高中数学教与学;2004年07期

10 刘康宁;两类多面体染色问题的解法[J];中学数学;1996年10期

相关会议论文 前1条

1 王继胜;;关于天然染料研究现状与设想[A];“五洋杯”2010年江苏纺织学术论文集[C];2011年

相关重要报纸文章 前10条

1 张裕;浅议弹性织物染色问题[N];中国纺织报;2003年

2 本报记者 刘伊婷;染色米中看不中吃[N];中国质量报;2005年

3 陈雍君;染色馒头不能只追究生产商责任[N];科技日报;2011年

4 ;纺织是高科技产业[N];中国工业报;2009年

5 记者　 张虎;“四新”会议突出染色主题[N];中国纺织报;2006年

6 河北省张家口市宣化区食品药品监督管理局 闫利霞;做好监管工作必须要有“几把刷子”[N];中国医药报;2013年

7 本版稿件由市老科技工作者协会提供;压力变动力创业做贡献[N];辽源日报;2005年

8 本报记者 韩竞;十年修炼终获大奖[N];中国纺织报;2005年

9 刘亚力 夏姗姗;中药材打假须整肃潜规则[N];中国中医药报;2013年

10 本报记者 俞春华 通讯员 陈守根;承诺重要,守诺更重要[N];中国石化报;2012年

相关博士学位论文 前10条

1 胡黎莉;符号图的整数流及染色问题研究[D];华中师范大学;2017年

2 周朝阳;图顶点染色问题中隐含约束关系研究与应用[D];华中科技大学;2017年

3 吕剑波;图的强边染色问题研究[D];华中师范大学;2018年

4 李善海;设计的染色及其相关问题的研究[D];上海交通大学;2006年

5 侯建锋;图上有限制条件的几类染色问题的研究[D];山东大学;2009年

6 陈敏;运用权转移方法研究图的若干染色问题[D];苏州大学;2011年

7 董爱君;图的几类染色问题[D];山东大学;2012年

8 胡小兰;极值和染色问题的一些新结果[D];南京大学;2015年

9 梁作松;图的团横贯与团染色[D];上海大学;2013年

10 孙林;平面图和1-平面图的若干染色问题[D];山东大学;2017年

相关硕士学位论文 前10条

1 刘佳;平面图的（3,0,0）-染色问题[D];山东师范大学;2018年

2 黄丽娜;图的若干可区别染色问题的研究[D];兰州交通大学;2018年

3 张宝晨;图的列表强边染色问题[D];山东大学;2018年

4 丁炀柳;不含4,5,7,8-圈的符号图3染色[D];华中师范大学;2018年

5 蓝俊;图的t-松弛染色问题研究[D];东南大学;2017年

6 王晔;1-平面图正常点染色问题的研究[D];山东师范大学;2017年

7 梁政;图染色问题应用研究[D];江西师范大学;2016年

8 王瑞琦;图边单射染色问题的复杂性及算法研究[D];南京师范大学;2014年

9 王辉;满足某些特殊条件的平面图边染色问题研究[D];山东大学;2010年

10 朱俊俏;关于图的点可区别染色问题[D];浙江师范大学;2009年

，

本文编号：2593461