平面图的边面染色及边面列表染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:lzy19900924
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
令G=(V,E,F)是一个无环的连通平面图,其中V表示点集,E表示边集,F表示面集.图G的一个边面k-染色是指存在一个映射π:E(G)∪F(G)→ {1,2,...,k},使得相邻的边染不同色,相邻的面染不同色以及相关联的边与面均染不同的颜色.图G的边面色数Xef(G),定义为使得G是边面k-可染的最小的正整数kk的值.这个概念最早由Jucovic和Fiamcik在1970年前后分别独立提出.数学大师Erdos和Vizing在上世纪60年代独立提出了列表染色的概念.平面图G是边面L-可染的是指图G有一个边面染色,使得对任意边或面所染的颜色都来自它的列表中.平面图G是边面k-列表可染的是指若对于任意满足|L(x)|≥k的列表L,其中x∈E(G)∪F(G),图G都是边面k-可染的.图G的边面列表色数x’ef(G),定义为使得G是边面k-列表可染的最小的正整数k的值.本学位论文主要研究了平面图的边面染色和边面列表染色问题,共分为三个章节,如下所示:第一章节,我们首先介绍本文所要用到的图论的基本概念和符号,然后简述与平面图的边面染色及边面列表染色相关的研究现状,最后给出本文的主要结果.第二章节,我们运用色延拓技巧和组合零点定理刻画了轮图的边面列表色数,并运用数学归纳法证明了每个满足△(G)≥6的哈林图是边面△(G)-列表可染的.第三章节,我们集中精力研究△=5的平面图的边面染色问题.Sanders和Zhao在2001年提出了一个猜想:若G是一个△≥3的平面图,则Xef≤△+2.并且,他们证明了 △(G)=3 和△(G)≥7 的情形.Chen,Raspaud 和 Wang 在 2014 年证明 了△(G)=6的情形,剩下△=4和△=5两种棘手情形.这一章,我们解决了 △=5的情况,即证明了△=5的平面图是边面7-可染的.
其他文献
细胞免疫治疗是近几年的研究热点,可用于细胞过继免疫治疗的细胞有T细胞、NK细胞等,NK-92细胞相比较于T细胞和NK细胞具有无MHC限制性和随取随用等优势,但是NK-92细胞并不能对
目的:根据手术入路的不同,探索在成人肱骨远端C型骨折的治疗中,尺骨鹰嘴的“V”形截骨入路与肱三头肌两侧入路(Alonso-Llames)这两种不同入路方式的疗效,综合比较二者各方面
近年来,多媒体产品不断发展,人们的需求增长变得越来越快,网络带宽不足问题和存储设备的存储容量不足问题变得日趋明显。要想加快图像的传输速率,或者减少图像存储所占用的空间,就要对图像进行压缩,减少图像中的冗余信息,以更加有效的形式存储或者传输数据,从而使得我们可以在获得相同视觉效果的同时,使用更少的原始图像信息。图像压缩根据解压效果可以将其分为无损压缩和有损压缩,一般情况下所研究的都是有损压缩算法。为
目的:观察双肺弥漫性病变患者支气管肺泡灌洗液(BALF)中KL-6、IL-35的变化;研究KL-6、IL-35在间质性肺疾病中的表达及临床意义;探讨KL-6、IL-35在间质性肺疾病中的应用价值。
目的:探讨实时剪切波弹性成像(shear wave elastography,SWE)技术鉴别子宫肌瘤与腺肌瘤的价值,找到并评估量化指标。方法:选取2018年8月至2020年1月就诊于河北医科大学第四医
本文研究与无中心的Ramond N=2李超代数?对应的一个秩为4的李共形超代数,称为Ramond N=2李共形超代数,记作C?.首先,构造?-值形式分布,计算它们满足的关系式,并确定共形集,再利用傅里叶变换定义λ-方括号,从而得到Ramond N=2李共形超代数。然后,计算Ramond N=2李共形超代数C?的共形导子和广义导子。根据C?的分次情况,在奇次和偶次的两种情形下,证得C?的共形导子和广
固体激光器在激光加工、激光雷达和光电对抗等领域具有广泛的应用,激光介质作为激光器的重要组成部分,是激光技术发展的核心和基础,研究并探索新型激光晶体的激光输出特性具有重要意义。本文中研究的新型混晶Nd:GdYTaO_4和Nd:GdYNbO_4与常用晶体相比较,对于输出1066 nm的激光上能级寿命更适中,具有高性能、高重频脉冲输出的潜力,本文从缓解激光晶体在泵浦作用下的热效应角度出发,采用直接泵浦方
Petri网作为一种有效的数学工具,被广泛应用于自动制造系统建模与分析。目前学者提出了多种死锁控制策略,但是大多数控制策略都假定制造系统无故障运行。然而,现实生产系统中许多设备资源在加工零件时可能会发生故障,这将导致已有控制策略失效。为了解决这一问题,本文针对S3PR(the system of simple sequential processes with resources)网以及GS3PR
葫芦素B(Cucurbitin B,CuB)是从自然界中广泛存在的葫芦科植物中提取、分离得到的一种四环三萜类化合物,具有保护肝脏、抗炎和抗肿瘤等生物活性,临床上用来治疗慢性肝炎及原发
目的多系统萎缩(multiplesystem atrophy,MSA)是一种中老年起病、散发性、病因不明的神经变性疾病,临床表现为不同程度的帕金森样症状、小脑性共济失调、自主神经功能损害、