平面图的DP-着色及图密接性的研究

来源 :华中师范大学 | 被引量 : 0次 | 上传用户:abchkiesh
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的着色问题一直以来是图论的热门经典问题.它最早起源于著名的“四色问题”,已广泛应用于信息论,计算机科学及人工智能等多个领域.本文研究了平面图的DP-着色以及图的密接性质,这主要属于四色问题的延伸范畴.全文共分八章,主要内容如下:在第一章,我们首先给出了文中所需的一些基本概念和符号,接着分别介绍了本文后续各个章节中所涉及的研究问题及背景.在第二章,我们介绍了 Borodin在1996年的一个有关列表着色的猜想:所有不含4到8-圈的平面图是3-可选的.Dvorak和Postle在2017年引入DP-着色的全新概念解决了这一长达20年的猜想,我们在这一结果的基础上做出改进,证明了不含圈长至多为8的相邻圈的平面图是3-可选的.在第三章,基于第二章的研究技巧,我们利用DP-着色试图解决平面图三色领域的相关热门问题.我们研究了平面图的DP-3-着色问题.我们把原先平面图在列表着色中的结果推广到了 DP-着色.我们通过构造一个“近-(k-1)-退化”的子图来解决在这一推广中所遇到的麻烦.在第四章,我们在第三章中给出的结果的基础上,进一步研究了不含{4,a,b,9}-圈的平面图,这里5≤α≠b≤8.我们证明了不含4,9-圈和两类圈长来自{5,6,7}的圈的平面图是DP-3-可着色的.在第五章,我们把研究的重点由三色问题进一步延伸到四色问题.我们围绕着Wang和Lih[54]在2002年提出的猜想:不含相邻三角形的平面图是4-可选的,证明了不含4-圈相邻两个3-圈的平面图是DP-4-可着色的.这一结果在往这一猜想迈进了一小步的同时也改进了 Kim和Yu[31]的结果.在第六章,我们还基于对平面图是DP-4-着色的充分条件的挖掘,证明了不含7-圈和蝴蝶结构的平面图是DP-4-可着色的.这一结果的证明给解决更多此方面相关问题提供了全新的方法,并且稍加改进可以极大的简化不含7-圈的平面图是4-可选的这一结果的证明.在第七章,上述内容主要研究着色数较小时的情况,本章我们研究了一般情况下,图染色方向的最著名猜想——Hadwiger猜想的相关问题.特别的,我们研究了这一猜想的最小反例的连通度性质,给出了一个图是密接的最小度条件.这一条件在对k-收缩-临界图的研究中起着至关重要的作用.在第八章,我们对本文所涉及的研究问题进行了归纳展望,提出了一些后续可以继续开展的研究方向.
其他文献
设μ为Rd上具有紧支撑的Borel概率测度.如果存在集合Λ使得指数函数族{e2πi:λ ∈ Λ}为L2(μ)的规范正交基,则称μ为谱测度,集合Λ为测度μ的谱.随着谱测度理论的不断发展,与其相关的问题已经成为分形几何与调和分析交叉研究的热点课题之一.本学位论文的主要内容分为两个主题:一是研究自相似测度的谱性;二是研究一类Moran谱测度的谱结构,即刻画其不同类型的谱(其中平移所得的谱视为同
一本“书”是由称为书脊的一条线和以书脊作为公共边界的半平面形成的页构成的.一个图G的书嵌入分为两步,首先,把这个图的所有顶点按照一定的顺序L(书脊序列)排列在书脊上(为了方便,我们把这个图的顶点集(V一一映射到{1,2,3,4,···,n}上);然后再分配这个图的每条边到一个单一页中,使得在同一页中的边是彼此不相交的.在书脊序列L下,如果在同一页中的两条边(a,b)和(c,d)是相交的,那么它们的
在标准模型中,粲介子的半轻子衰变过程中的强、弱作用能够很好地被分离处理,因此,理论上比较容易计算它们的跃迁率。其衰变振幅正比于CKM矩阵元与强子弱流形状因子的乘积,其中,CKM矩阵元表征弱相互作用中不同夸克的跃迁几率,而形状因子则描述终夸克之间的强相互作用。在实验上研究粲介子的半轻子衰变对理解弱衰变过程中的非微扰强相互作用动力学有重要作用。三十年前,夸克模型曾预言了D介子到S波和P波的一系列半轻跃
路和圈是结构图论的重要研究课题之一,对其进行研究不但有重要的理论意义,而且在计算机科学、信息科学和生物科学中有广泛的应用.确定一个图是否为哈密尔顿图是NP-困难的.由于其和四色定理的密切联系,以及较强的应用性,图的哈密尔顿性一直是图论研究的中心问题之一.本论文主要研究二部图中的圈结构和路结构.全文共分四章,主要内容如下:在本文第一章,首先介绍了文中出现的一些基本定义与符号.接着阐述了研究背景、研究
目的分析嗜酸细胞性胃肠炎临床表现的多样性及非特异性。方法对2例EG患者的病史、临床表现、生化和内镜检查结果进行分析,结合文献复习,分析EG患者的临床特点。结果嗜酸细胞性胃肠炎的临床表现缺乏特异性,与其病变部位及累及深度有关。结论嗜酸细胞性胃肠炎临床表现多样,确诊需有病理证实,激素治疗有效。
生物传感器是一门由生物、化学、物理、医学、电子技术等多种学科互相渗透成长起来的高新技术,具有选择性好、灵敏度高、分析速度快、成本低、在复杂的体系中进行在线连续监测,特别是它的高度自动化、微型化与集成化的特点,使其在近几十年获得蓬勃而迅速的发展,成为现代生物技术的重要支撑。随着纳米技术的飞速发展,研究表明,由于纳米材料具有独特的光学、电学和催化特性以及良好的生物相容性,将纳米材料应用到生物传感器的制
图的支撑树特征问题一直是结论图论研究中的一个重要课题。该问题的产生与发展都与结构图论中的经典问题一一哈密尔顿问题有着密切联系。众所周知图G中含哈密尔顿路当且仅当G中含至多两个叶子点的支撑树。一个自然的问题是:对于任意的整数k ≥ 2,在何条件下G中存在至多k个叶子点的支撑树?目前国内外对满足一定条件的支撑树存在性问题的研究主要是从参数的角度,如坚韧度、独立数、连通度、度和等方面进行刻画,或者限制在
本文主要探讨了两类偏微分方程解的奇异极限问题,即研究当参数趋于零时抛物型Allen-Cahn方程和椭圆型Sinh-Poisson方程的解的收敛性.我们利用几何测度论的相关理论建立了 Allen-Cahn方程解的收敛性,运用Lyapunov-Schmit有限维约化方法研究了 Sinh-Poisson方程集中解的存在性.本文共分三章:在第一章,我们概述了本文所讨论问题的研究背景及国内外研究现状,并简要
本文我们主要研究拟周期线性斜积系统(拟周期线性Cocycle)的局部约化的刚性、全局约化的刚性问题,以及拟周期非线性斜积系统(拟周期驱动的环面流)的线性化问题.第一章,介绍本论文中涉及的基本符号和概念.我们首先介绍函数空间与范数;然后介绍研究对象:拟周期线性斜积系统、拟周期驱动的环面系统;其次介绍基本概念:Lyapunov指数和旋转数,可约与可线性化,以及一些数论上的概念和性质;最后我们介绍有限光
这篇论文中我们考虑七个拓扑余指标:第一、二类Zagreb coindices,第一、二类 multiplicative Zagreb coindices,the F-coindex,第三 Zagreb coindex 和the hyper Zagreb coindex.全文分为三个部分:第一部分利用结构分析和求导研究分子图(benzenoid graphs、graphene sheet and C