有限制条件的两个图染色问题

来源 :山东师范大学 | 被引量 : 0次 | 上传用户:dl_smh
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
给定一个图(G=(V,E),图G的正常染色是指对G的每个顶点(边)分配一种颜色,使得相邻的两个顶点(边)染不同的颜色.满足图G是正常m-可染的最小正整数m,称为图G的色数(边色数),记为x(G)(x’(G)).图G的单射(injective)k-染色是指映射C:V(G)—→{1,2,…,k}使得有公共邻点的两个顶点u,v满足C(u)≠C(v).满足图G有一个单射k-染色的最小正整数k,称为图G的单射染色色数,记为xi(G).图G的一个列表分配是一个映射L,使得每个顶点分配一个颜色列表L(v).给定图G的一个列表分配L,若一个单射染色C满足(?)v∈V(G),C(v)∈L(v),则称C是图G的一个单射L-染色.若对图G的任意一个满足|L(v)|≥k的列表L,都有一个单射L-染色,则称G是单射k-可选的.满足图G是单射k-可选的最小正整数k,称为图G的单射可选数,记为xil(G).我们证明若图G是g(G)≥5且最大度为Δ的平面图,则xil(G)≤max{Δ+4,14}.图的强边染色是一种正常边染色,要求任何长至多为3的路上的边都染不同的颜色.满足图G有一个κ-强边染色的最小正整数k,称为图G的强边色数,记为xB1(G).如果图G既不含P5又不含C5作为导出子图,则称为图G是(P5,C5)-free的.本文中我们证明若图G是(P5,C5)-free的且最大度为Δ,则我们研究了平面图的单射染色问题和强边染色问题.本论文共分为四章.第一章,我们介绍图的单射染色和强边染色问题的背景及主要进展,给出本文中用到的基本概念与符号和列出本文中的主要结果.第二章,我们证明若图G是g(G)≥5且最大度为△的平面图,则xil(G)≤max{Δ+4,14}.第三章,我们证明若图G是(P5,C5)-free的且最大度为Δ,则第四章,我们给出可进一步研究的问题.
其他文献
伴随我国社会经济的发展,建筑的空调系统(供热和供冷)占到社会总能耗的25%~30%,传统能源存在环境污染等弊端,清洁能源的开发迫在眉睫。在各种新能源和可再生能源中,地球地表下包含存储的地热能源能有效应用于空调系统。本文基于地热开发的能源桩技术提出了一种新型的深层埋管式能源桩技术,该技术不仅充分利用桩内埋管式能源桩的优点,并且可利用更深层地热来提高单根能源桩换热量。新型能源桩的结构形式灵活,能够根据
21世纪初,中国的城市化进程呈逐年递增趋势,截止2019年,中国的城市化率已达五成以上,这意味着中国的城市化迈入了一个新的历史阶段。2015年牡丹江市对A社区进行了初步网格化,
太赫兹波位于微波段和光波段之间,当前没有大规模的应用,本文主要以太赫兹波的应用为背景,通过理论计算和实验测量两种方式对目标太赫兹散射特性进行研究,揭示太赫兹频段目标散射特性的影响因素。针对常见算例利用不同的计算方法,由于太赫兹频段的特殊性,主要从电磁方法和光学方法两个方面对其散射特性进行研究,为太赫兹频段目标电磁散射提供仿真和测试两方面的数据支持,具有一定的理论和应用价值。本文创新性的给出太赫兹频
现代移动通信以第一代移动通信技术的发明为标志,在经历爆发式增长后,对人们的生活方式产生巨大的影响。如今,移动通信渗透到生活的方方面面,成为推动社会发展的重要因素之一。5G作为新一代移动通信技术,将广泛应用于增强移动带宽(enhanced Mobile BroadBand,eMBB)、高可靠低时延通信(Ultra-reliable and Low Latency Communication,URLL
无线通信技术的快速发展,促使了各类新型应用的产生,运营商提供的服务类型也在飞速的扩展,如短视频、在线直播等等,此时服务类型由传统的“以连接为中心”的服务转变为了“以内容为中心”的服务。这些服务需求不仅有高数据传输效率、低传输时延的要求,同时也需要大量的计算能力和持续的数据处理能力。要想最大化利用有限的无线频谱资源,优秀的资源分配算法是提高整个网络性能的关键,而传统的资源分配算法很难同时满足这些需求
随着城市居民的生活品质和电气化程度的逐渐提高,作为与电网用户联系最为紧密的配电网的建设与发展,在新时代背景下面临着诸多的问题与挑战。配电网重构不仅作为提高系统电能质量、供电可靠性与灵活性的重要手段,也在减小网络损耗、提高运行经济性等方面发挥着关键作用。由于分布式电源(Distributed generation,DG)具有良好的环境效益和经济效益,DG已被广泛地应用于配电网中,但是随之而来的功率倒
随着人工智能的高速发展,自然语言处理等计算机技术获得了极大关注,具有很强的研究潜力。文本生成在自然语言处理领域有着重要意义,高质量的文本对于对话系统、智能翻译、文学写作、知识图谱等与自然语言处理相关的任务具有重要影响作用。文本数据由于自身的离散性和语义结构自身的复杂性,容易出现文本训练数据样本数量少、质量差、样本缺失等难题。现有的文本生成技术的研究已经有了较大的进展,但是仍存在着一定的局限性。例如
日常生活中存在着很多二分网络结构,譬如用户-域名网络,云服务中相互承载的源IP-域名网络等等。二分网络中存在着社团结构,基于社团结构的网络分析比基于节点的网络分析更为高效。同时,社团结构的发现可以检测出匿名网络中潜在的威胁,这对二分网络的管理以及分析意义重大。但是随着大数据时代的降临,企业每天产生的日志量呈爆炸式的增长,传统的社团发现方法并不能适用于长时间尺度内海量的日志数据,这使得对长时间尺度内
分数阶最优控制问题由于其在地下水污染等实际问题中的广泛应用,在理论模型和数值方法方面的研究得到了越来越多的关注.本文主要研究两类控制积分约束的空间分数阶最优控制问
汽车已经成为人们生活中不可或缺的一部分,而汽车拥有量的急剧增加使得交通拥堵、交通安全、空气污染等问题愈加严重。人们逐渐将路径规划、行车安全、网络互娱等元素加入到汽车产业当中。在这样的需求条件下,智能交通系统(ITS,Intelligent Transportation System)的发展迫在眉睫。车联网技术作为智能交通系统中最重要的组成部分,主要包括车辆与路旁基础设施(V2I,Vehicle t