关于不含5-圈相邻6-圈或相交5-圈平面图的DP-4-着色问题

发布时间：2023-02-06 12:52

　　图论是数学的一个分支,是近年来发展迅速而又应用广泛的一门学科.染色问题是图论中十分活跃的研究课题,有着深刻而丰富理论结果和广泛的实际应用,其理论和方法在离散数学中占有重要地位.本文证明了不含5-圈与6-圈相邻的平面图是DP-4-可着色的,并且还证明了每个不含相交5-圈的平面图是DP-4-可着色的.具体内容包括:·第一章介绍论文的研究背景、研究意义、国内外学者对这方面的研究状况,以及一些相关引理和本文需要证明的定理.通过对研究背景及研究现状的深入分析,充分说明了本文研究工作的必要性和创新点.·第二章介绍本文涉及到的基本概念和符号.·第三章为了证明定理1.3,本章节证明了更强的结果,见定理3.1,然后用定理3.1来证明定理1.3.假设(G,C0)是定理3.1的最小反例,其|V(G)|最小,此处C0是图G中的预着色k-圈,其中k=3,4.如果C0是一个分离圈,则C0的任何预着色可以分别延拓到int(C0)和ext(Co).然后得到了图G的一个DP-4-着色,得出矛盾.本章节研究了最小反例图G的一些结构特征,找到并证明图G不存在的可约构形.然后根据找到的可约构形制定恰当的权转移规则,用权转移规...

【文章页数】：39 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 引言
    1.1 研究背景、研究意义及国内外研究成果
    1.2 本文主要结果和相关结论
第二章 预备知识
第三章 定理1.3的证明
    3.1 坏4-圈的介绍
    3.2 定理1.3的证明
    3.3 最小反例的结构性质
    3.4 权转移规则
    3.5 检查权转移后图(G,C₀)所有点和面的权
第四章 定理1.4的证明
    4.1 定理1.4的证明
    4.2 最小反例的结构性质
    4.3 权转移规则
    4.4 检查权转移后图(G,C₀)所有点和面的权
第五章 总结展望
参考文献
致谢



本文编号：3736033