【摘 要】
：
图的染色理论起源于著名的四色猜想,是图论领域中重要的研究方向之一,在组合优化、编码计算及交互网络等方面有着重要的应用.本文主要研究图的无圈染色、无圈列表染色和无圈列表边染色问题.如果图G的一个正常点染色f使得G中不含双色圈,则称f为G的无圈染色,其色数用a（G）表示.如果图G的一个正常边染色f使得G中不含双色圈,则称f为G的无圈边染色,其色数用a’（G）表示.类似地,如果图G的一个列表染色f使得G
【基金项目】
：
国家自然科学基金11771443；
论文部分内容阅读
图的染色理论起源于著名的四色猜想,是图论领域中重要的研究方向之一,在组合优化、编码计算及交互网络等方面有着重要的应用.本文主要研究图的无圈染色、无圈列表染色和无圈列表边染色问题.如果图G的一个正常点染色f使得G中不含双色圈,则称f为G的无圈染色,其色数用a（G）表示.如果图G的一个正常边染色f使得G中不含双色圈,则称f为G的无圈边染色,其色数用a’（G）表示.类似地,如果图G的一个列表染色f使得G中不含双色圈,则称f为G的无圈列表染色,其色数用al（G）表示.如果图G的一个列表边染色f使得G中不含双色圈,则称f为G的无圈列表边染色,其色数用al’（G）表示.另外,用Δ表示图G的最大度.无圈染色源自图的划分问题:求图的顶点集能够分成导出子图为森林的不交子集的最少个数.1973年,Grunbaum首次给出了无圈染色的概念,并且提出了著名的无圈染色猜想:每个图G的无圈色数a（G）≤ Δ+1.2001年,Alon等提出了著名的无圈边染色猜想:每个图G的无圈边色数a’（G）≤Δ+2.本文主要围绕以上两个猜想,针对最大度Δ较小的图的无圈染色、无圈列表染色以及无圈列表边染色问题进行研究,全文共分为五章.第一章,简述研究背景、研究现状、图的基本概念及本文的主要结果.第二章,研究图的无圈染色,得到了以下结果:1.证明了最大度Δ ≤ 6的图G的无圈色数a（G）≤ 9,从而改进了 Zhao等（2014）的结果 a（G）≤ 10;2.证明了最大度Δ ≤ 7的图G的无圈色数a（G）≤ 12,从而改进了 Dieng等（2010）的结果 a（G）≤ 17.第三章,研究图的无圈列表染色,得到了以下结果:1.证明了最大度Δ ≤ 5的图G的无圈列表色数al（G）≤7,从而将Kostochka等（2011）的结果推广到无圈列表染色;2.证明了最大度Δ ≤ 6的图G的无圈列表色数al（G）≤10,从而将Zhao等（2014）的结果推广到无圈列表染色;3.证明了最大度Δ ≤ 7的图G的无圈列表色数al（G）≤13,从而将Dieng等（2010）的结果推广到无圈列表染色并降低了需要的颜色数;4.给出了最大度Δ ≤ 3的图G的无圈列表色数al（G）≤ 4和最大度Δ≤4的图G的无圈列表色数al（G）≤ 5更简捷的证明.第四章,研究图的无圈列表边染色,得到了以下两个结果:1.证明了最大度Δ ≤ 4的图G的无圈列表边色数al’（G）≤7;2.证明了最大度Δ ≤ 4且边数|E（G）|≤2|V（G）|—1的连通图G的无圈列表边色数al’（G）≤6.从而将Basavaraju和Chandran（2009）的结果,从无圈边染色推广到无圈列表边染色.第五章,总结全文,并展望进一步的研究方向和潜在的研究工作.
其他文献
本文研究了非线性数学物理中的几类非线性微分方程的可积耦合、Hamilton结构、Darboux变换和精确解。主要开展了四个方面的研究工作:离散晶格系统的Hamilton结构和守恒律;基于Bell多项式的非线性偏微分方程的可积性质;可积耦合及其约化;（2+1）-维可积系统的Darboux变换和精确解。第一章,主要介绍了与本文相关的R-矩阵理论、非线性偏微分方程的精确求解和可积系统理论的研究背景及发展
2018年,国网江西检修公司坚决贯彻国网江西省电力有限公司各项决策部署,在安全生产方面狠抓安全责任落实,编制全员安全责任清单,确保安全局面稳定;充分发挥智能巡检优势,变电站智能巡检机器人在19座500千伏变电站应用,无人机对"三跨"区段开展精细化巡视,发现缺陷329项,运检管控质量显著增强;开展党支部结对共建,促进党建管理水平提升。截至10月31日,实现江西主网安全稳定运行3535天,未发生
介绍无人机、数码相机、三维激光扫描等近景摄影测量手段在石窟寺调查中的相关测量手段的应用研究,首先对比分析了传统测量手段和现有多种近景摄影测量手段的优缺点,并分别介绍了3种方法的测量技术作业流程、数据处理分析流程和成果精度验证分析等,验证了3种文物立面施测方法在不同环境中作业的可行性与精度等级。
竣工测量是城市规划管理、智慧辅助决策的基础工作,随着智慧城市建设步伐的加快,通过传统全野外数字采集方法获取的二维竣工数据已难以满足新时代发展对基础数据三维化的新要求。以竣工项目为例,通过倾斜摄影测量、三维激光扫描技术与传统全野外数字采集方法的对比,在精度、效率指标等方面探讨新兴测量方法在竣工测量工作中的可行性和适用性,旨在为传统二维全野外数字采集技术向二、三维数据采集技术的融合提供参考。
上消化道出血在临床上非常多见,其病因有溃疡病、慢性胃炎、血吸虫病肝纤维化、肝炎后肝硬化门静脉高压等。对上消化道出血的治疗大都是用禁食、补液及各种止血剂的综合性措施。门静脉高压病人插三腔管、输血等治疗,在实践中碰到上述治疗无效而手术治疗又缺乏条件的病人,我院自1980年以来曾先后选用以生大黄治疗110例上消化道出血病,临床取得了满意效果,今分析如下。
我国在能源方面具有“富煤、少气、缺油”的特点,能源消费的增长与传统化石能源资源的不足以及生态环境的保护之间的矛盾日益剧烈,对如何更加合理的使用能源资源提出了更高的要求。对低品质褐煤进行有效的脱水提质是实现煤炭清洁高效利用的重要途径,抑制提质褐煤对水分的复吸将可以大大提高褐煤的利用效率。随着水热处理工艺技术的日渐成熟,HTC技术将成为是一种极有前途的褐煤提质措施。本文以贵州隆昌褐煤为实验研究对象,研
非线性常微分方程边值问题是微分方程定性理论中一个重要分支,具有广泛的应用背景.近年来,随着分数阶微积分理论的发展,分数阶微分方程在许多领域被广泛的应用,如:物理力学领域、反常扩散研究领域、自动控制领域、生物医学领域等.从而对分数阶微分方程边值问题的研究受到人们的重视,得到了许多深刻的结果.本文在已有工作的基础上,利用推广的集值映射型Leggett-Williams定理、改进的k-集压缩算子抽象连续