1-平面图正常点染色问题的研究

来源 :山东师范大学 | 被引量 : 0次 | 上传用户:lconan
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文主要研究的是简单有限图.图的点染色是对图G的顶点集的一种剖分.如果图G的顶点集V可以剖分成互不相交的k部分,给每一部分染上同一种颜色,不同部分所染的颜色不同,若剖分产生的各部分都是点独立集,则图G是正常点染色.若图 G存在一个顶点集到颜色集的映射φ: V(G)?→{1,2,···,k},对于G中的任意两个相邻的点u和v,φ(u)=φ(v),则称φ是图G的一个k染色又称图G是k-可染的.图的色数是指一个图正常点染色所用的最少颜色数.  一个图被称为1-平面图当且仅当它可以画在一个平面上,使得它的任何一条边最多交叉另外一条边.1986年,Borodin在[14]中证明了1-平面图是6-可染的.2005年,1-平面图是否是4-可染的被证明是NP-完备的.2016年,宋立莉在[10]中证明不含4-圈以及5-点不与5-点相邻的1-平面图是5-可染的.  本文共分三章,主要讨论的是加了某些限制条件的1-平面图的正常点染色问题.  在第一章中,主要介绍了论文所涉及的有关概念和符号以及本文的研究背景和已有的一些结果.在第二章、第三章中将平面图的正常点染色研究推广到了1-平面图的正常点染色研究,证明了:围长至少是5的1-平面图是5-可染的.不含4-圈5-圈和6-圈的1-平面图是5-可染的.
其他文献
框架是标准正交基的一种推广,它在许多应用中弥补了标准正交基的不足.典型的如在信号处理中,若以标准正交基处理信号,一旦出现数据部分丢失,完整的原信号将无法被重构.这种情况下
对偶是现代数学中一个极为普遍而且重要的概念,几乎在数学的每一个分支都有应用.本论文主要研究马尔可夫过程的对偶方法,重点对三种对偶进行了详细讨论,即单调对偶、矩对偶和拉普
最近,为求解三维二阶椭圆边值问题,Meng,Sheen,Luo[5]构造了一种新的立方体上的低阶非协调元。本文用这种新的非协调元和P1非协调元组成新的混合元对来求解Stokes方程。为使所构
矩阵理论在统计学、梯形网络、运输理论、动态规划、控制理论和统计过滤等领域中有着广泛的应用.连续线性系统稳定分析和最优控制问题设计中的许多问题常常可转化为线性矩阵方
在这篇论文中,我们通过水平集方法(level-set)和浸界面方法(IIM)来研究含表面活性剂的两液滴在二维伸张流的条件下的数值结果。我们发现表面活性剂在两液滴的相互作用中扮演了非常
近年来,分数发展方程的研究己取得了许多新的进展.但是,相对于理论体系完整的整数阶微分方程而言,分数阶微分方程在理论方面的研究还很不完善,有许多领域尚未涉及,需要我们进一步研
两服务台的排队系统是多服务台排队系统中最简单的情形,在生产和实际生活中占有很重要的地位。特别是在引入某些条件后,使得模型能更加具体、更加贴近实际,因此研究具有一定的价
带关联矩阵的NUAH B样条曲线是基于空间{1,t,..., tn-3,sinht,cosht}生成的一类特殊的样条曲线,它具有很多和多项式B样条曲线相类似的性质,并且能表示一些如螺旋线、摆线等多项
本文介绍了变化环境下配对函数依赖祖先配对数的受控两性分支过程,这是一种特殊意义下的两性G-W分支过程,能更加如实合理地描绘自然界生物种群繁衍过程中的不同现象,并对此过程
在这篇论文中,我们研究的是有表面活性剂的液滴在拉伸流的数值模拟。我们在文章中运用了一种解决这种问题的数值方法-水平集连续表面力方法。  水平集连续表面力方法的提出