图的松弛强边染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:green7116xxx
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
令G是一个有限简单图且k是正整数.用V(G),E(G)以及F(G)分别表示图G的顶点集,边集以及面集,简记为V,E和F.若存在映射π:E{1,2,...,k},使得E中任意两条相邻边e和e’,都有π(e)≠π(e’),则称π是图G的一个正常的k-边染色,并称G是正常k-边可染的.图G的边色数χ’(G)定义为使得G是正常k-边可染的最小正整数k的值.若存在映射π:E(G)-→ {1,2,...,k},使得E中任意两条距离至多为2的边e和e’,都有π(e)≠π(e’),则称π是图G的一个强边k-染色,并称G是强边k-可染的.图G的强边色数χs’(G)定义为使得G是强边k-可染的最小正整数k的值.给定两个非负整数s和t.若存在映射π:E(G)-→ {1,2,...,k}使得G中任意一条边e,满足其颜色π(e)在它的1-邻域中至多出现s次,且在它的2-邻域中至多出现t次,则称π是G的一个(s,t)-松弛强边k-染色,并称G是(s,t)-松弛强边k-可染的.图G的(s,t)-松弛强边色数χ(s,t)’(G定义为使得G是(s,t)-松弛强边k-可染的最小正整数k的值.给图G中的每条边e配置一个颜色集合L(e),记L={L(e)| e ∈E}.如果存在一种正常边染色π,使得π(e)∈ L(e),那么称G是L-边可染或称G有一个L-边染色.若对所有的e ∈E(G),对于任意配置的列表L,其中|L(e)| ≥k,G都是L-边可染的,则称G是k-边列表可染的.我们把使得G是k-边列表可染的最小正整数k的值定义为G的边列表色数,记作ch’(G).若存在一个强边染色π,使得对每条边e都有π(e)∈ L(e),则称G是强边L-可染的.同时染色π被称作G的一个强边L-染色.类似地,当|L(e)| ≥ k且G是强边L-可染的,称G是强边列表k-可染的.G的强边列表色数定义为使得G是强边列表k-可染的最小正整数k的值,记作chs’(G).若存在一个(s,t)-松弛强边染色π,使得对每条边e都有π(e)∈ L(e),则称G是(s,t)-松弛强边L-可染的.同时染色π被称作G的一个(s,t)-松弛强边L-染色.类似地,当|L(e)| ≥ k且G是(s,t)-松弛强边L-可染的,称G是(s,t)-松弛强边k-列表可染的.G的(s,t)-松弛强边列表色数定义为使得G是(s,t)-松弛强边k-列表可染的最小正整数k的值,记作ch(s,t)’(G).2017年,He和Lin首次提出了图的(s,t)-松弛强边染色问题.近年来,图的(s,t)-松弛强边染色问题引起了国内外研究者的极大关注.注意到,若s=t=0时,对应为人们熟知的强边染色问题.因此,(st)-松弛强边染色问题是强边染色的一种自然推广.本学位论文主要围绕此课题展开研究.我们将给出在围长限制条件下的平面图的(1,0)-松弛强边列表染色的一些结果.论文框架结构及内容如下:在第一章中,我们将先给出本文用到的一些基本概念,然后简述相关领域的研究现状和本文的研究结果.在第二章,第三章和第四章中,我们均运用反证法,通过构造极小反例,运用色延拓技巧以及经典的权转移方法,分别证明了以下三个结果:(1)如果G是一个围长至少为6的平面图,那么ch’(1,0(G)≤ 3△(G)-1.(2)如果G是一个围长至少为7的平面图,那么ch’(1,0(G)≤ 3△(G)-2.(3)如果G是一个围长至少为9的平面图,那么ch’(1,0(G)≤ 3△(G)-3.
其他文献
近年来,多媒体产品不断发展,人们的需求增长变得越来越快,网络带宽不足问题和存储设备的存储容量不足问题变得日趋明显。要想加快图像的传输速率,或者减少图像存储所占用的空间,就要对图像进行压缩,减少图像中的冗余信息,以更加有效的形式存储或者传输数据,从而使得我们可以在获得相同视觉效果的同时,使用更少的原始图像信息。图像压缩根据解压效果可以将其分为无损压缩和有损压缩,一般情况下所研究的都是有损压缩算法。为
目的:观察双肺弥漫性病变患者支气管肺泡灌洗液(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)是一种中老年起病、散发性、病因不明的神经变性疾病,临床表现为不同程度的帕金森样症状、小脑性共济失调、自主神经功能损害、
令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年前后分别独立提出.数学
内蒙古翁牛特旗位于大面积荒漠草原到森林农田的过渡带,属特殊地质地貌区中的荒漠草原浅覆盖区,大地构造位置位于华北板块北缘,是兴蒙造山带与华北克拉通北缘的叠加部位,区域上属于西拉沐沦成矿带的东段,是大兴安岭成矿带南段的重要组成部分,区内成矿期次多、强度大而且成矿类型多样,具备良好的成矿条件与找矿前景。因此,很有必要对研究区开展成矿条件研究,进而提出找矿方向。但是由于研究区属于浅覆盖区,可直接观察的基岩