平面图的多重染色和边赋权染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:zkc19890314
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文主要研究了平面图的两类染色问题:一类是平面图的多重染色,一类是平面图的边赋权染色.图G的一个b-重染色是给G的每个顶点〃分配一个含有b-个颜色的集合φ(u),使得对任意的边e=uv,φ(u)∩φ(u,=(?).如果对G的任意一个a-列表配置L,G都有一个b-重染色φ满足φ(v),(?)L(v),则称G是(a,b)-可选的.如果对任意的正整数b,G是([rb],b)-可选的,则称G是强r-分数可选的.我们定义G的强分数选择数为chf*)(G)=inf{r:G是强r-分数可选的}.对于图类g,令 chf*(g)=sup{chf*(G):G ∈g}.最近,Zhu[28]证明了对任意的正整数m,存在一个平面图不是(4m+[2m-1/9],m)+可选的;随后,Jiang和Zhu[11]证明了对任意的正整数m,存在一个没有3-圈的平面图不是(3m+[m/17],m)-可选的.令P表示平面图全体,令Pk表示不含k-圈的平面图全体.上述结果蕴含有chf*(P)≥4+2/9,chf*(P3)≥3+1/17.本论文研究了没有4-圈的平面图和没有5-圈的平面图的强分数选择数.我们证明了对任意的正整数m,存在一个没有4-圈的平面图不是(3m+[m/2],m)-可选的.对任意的正整数m,存在一个没有5-圈的平面图不是(3m+[m/4]-1,m)-可选的.所以,chf*P4)≥ 3+1/2,chf*(P5)≥3+1/4.在第二章我们给出了这两个结果的详细证明过程.图的边赋权染色的概念是Karonski,Luczak和Thomason[14]在2004年引进的.Karonski,Luczak和Thomason在[14]中提出了如下猜想:对任意不含孤立边的图G,存在G的一个边赋权w:E(G)→{1,2,3},使得对任意相邻的两个顶点u,v,有∑e∈E(u)w(e)≠∑e∈E(v)w(e).这一猜想近十多年来受到极大的关注,被称为1-2-3-猜想.我们称满足上述条件的边赋权w为G的一个3-边赋权点染色.Karonski,Luczak和Thomason证明了不含孤立边的3-可染的连通图满足1-2-3-猜想.2010年Kalkowski,Karonski和Pfender[13]证明了不含孤立边的连通图,存在一个5-边赋权点染色.2017年,Wu,Zhang和Zhu[27]等人证明了 4-可染的4-边连通图,存在3-边赋权点染色.Lyngsie,Thomassen和Zhong[17]在1-2-3-猜想的基础上提出了一个强化4-色定理的猜想:对任意不含孤立边的平面图G,存在G的一个边赋权w:E(G)→{1,2,3},使得对任意相邻的两个顶点u,v有∑e∈Eu(u)w(e)≠∑e∈E(u)w(e)(mod 4).我们称满足上述条件的边赋权w为G的一个3-边赋权4-染色.这是一个比4-色定理强很多的猜想.Lyngsie等人证明了4-可染的4-边连通图和三角化的平面图满足这个猜想.在本文中我们证明了阶数至少为3的树满足这个猜想.利用4-色定理,我们证明了每一个平面图G存在一个4-边赋权4-染色.另外,我们证明了每一个不含孤立边4m-可染的图G,存在一个4m-边赋权4m-染色.
其他文献
铜配合物由于其良好的发光特性被视为其他贵金属配合物的替代品,在染料敏化太阳能电池(DSSC)的研究中取得了极大进展。本文以Cu(I)配合物的研究为主题:以提高铜配合物的在可见光区吸光能力、延长激发态寿命为目标,设计开发了具有不同发色基团的Cu(I)配合物。以2-吡啶基咪唑配体为切入点,通过核磁、紫外可见吸收光谱、荧光发射光谱、激发态寿命以及量子产率等表征手段,探究了不同取代基的吡啶基唑类配体对配合
目的:研究静脉注射紫杉醇对肺高压大鼠肺动脉压力、肺血管重构及肺血管周围炎症的作用。研究方法:100只雄性Sprague Dawley(SD)大鼠(由南京医科大学提供,220-250 g),随机分成
近年来,由于比色和荧光检测方法与传统分析方法相比具有即时响应,选择性好,高灵敏度,低花费,易于操作等优良特性,被广泛报道。在众多报道的比色和荧光化学传感器中,发现基于二芳烯类的比色和荧光传感器吸引了众多研究者的关注,这是由于二芳基乙烯类化合物本身具有优于其他光致变色材料的优良特性,如卓越的热稳定性,优异的抗疲劳性以及快速响应等被称为最具有潜力的光致变色材料。然而大多数的二芳烯类比色或荧光传感器仅能
目的:探究绝经后女性血清中高密度脂蛋白胆固醇(HDL-C)和高密度脂蛋白颗粒(HDL-P)的水平与冠状动脉粥样硬化程度之间的相关性。方法:收集2018年11月1日至2020年1月1日在青海
目的:评价薏苡仁汤治疗风寒湿痹型膝骨关节炎的临床疗效和安全性。方法:采用回顾性研究,收集2018年6月至2019年8月期间于成都中医药大学附属医院骨科门诊就诊并分别服用薏苡
本学位论文仅考虑有限、简单且无向图.给定一个图G,我们分别用V(G),E(G),F(G),△(G)和g(G)来表示它的顶点集、边集、面集、最大度和围长.图G的强kk-边染色是指一个映射φ:E(G)→{1,2,...,k},若e1,e2 ∈E的距离至多为2,有φ(e1)≠φ(e2).称χs(G)=min{k| G有一个强kk-边染色}为G的强边色数.1989年,图的强边染色上界的一个著名猜想由Erd
食品会因芽孢的存在而引发腐败及一些安全问题,但是芽孢却又很难被各种杀菌方法杀灭,所以找到杀灭芽孢的路径迫在眉睫。造成芽孢死亡的关键之处在于芽孢皮层肽聚糖水解,由于芽孢萌发、核心水化、皮层裂解酶被激活,所以芽孢抗性消失,故将皮层裂解酶分离纯化出来就显得尤为重要。从天然菌种中提取皮层裂解酶,工作量大、难以分离纯化且产率还低,所以本文通过基因工程操作技术,构建了皮层裂解酶CwlJ的基因工程菌,以获得大量
黄芩来源于唇形科植物黄芩(Scutellaria baicalensis Georgi)的干燥根,是我国传统中药,应用广泛,具有清热燥湿、泻火解毒、止血安胎之功效,其主要有效成分是黄芩苷。黄芩苷具
念珠菌作为一种条件致病菌是引起真菌性奶牛乳房炎的主要病原菌之一。念珠菌致病性强弱与其毒力因子的携带情况有关,这些毒力因子主要有二相性、溶血活性、细胞表面疏水性和
聚类在数据挖掘、机器学习以及模式识别等领域有着非常广泛的应用,聚类分析是一种针对无标签数据的无监督学习方法。聚类集成的优势在于能够组合多个聚类成员以提供更好的聚