图的点划分及其相关问题

来源 :山东大学 | 被引量 : 0次 | 上传用户:lizhuang1022
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的点划分问题是图论研究中非常重要的研究课题。图的点划分问题是指把图的顶点集划分成一些互不相交的点子集的并,使得划分之后的子集或者子集之间满足某些条件。图的点染色问题可以看成是把图的顶点集划分成一定数目的独立集的不交并。Erd?s-Lovász Tihany猜想研究的是对于满足一定条件的图,可以把它的顶点集划分成两个不交的子集,使得这两个子集的导出子图的点色数足够大。本论文首先对图的列表分离染色进行了研究,接着围绕Erd?s-Lovász Tihany猜想展开了一些探讨。所得结果具有一定的理论意义。给定一个图G,列表L指的是图G中的每个点v到它的颜色集合L(v)的一个映射,即给图G中每个点v分配一个颜色的集合L(v)。如果图G中的每个点可以从它的点颜色列表L里选择颜色对其进行染色,使得相邻两个点染不同的颜色,则称图G存在L-染色,或称图G是L-可染的。如果图G对于任意的列表L都存在L-染色,其中对任意的点v∈ V(G),L满足|L(v)|≥ k且对于任意的边xy ∈(G),L满足|L(x)∩L(y)|≤d,则称图G是(k,d)-可选的。这个概念是Kratochvíl,Tuza和Voigt在1998年提出的,同时他们证明了:所有的平面图都是(4,1)-可选的。根据Thomassen证明的结果:平面图是5-可选的。因此所有平面图也是(5,d)-可选的,其中d∈{1,2,…,5}。此外,Berikkyzy等人证明了不含弦l-圈的平面图是(4,2)-可选的,其中l∈{5,6,7}。Choi等人证明了不含4-圈的平面图是(3,1)-可选的,以及不含5-圈和6-圈的平面图也是(3,1)-可选的。本文证明了以下结果:(1)如果图G中的任意i-圈不与j-圈相邻,那么G是(3,1)-可选的,其中5≤i≤6,5≤j≤7。(2)对于不含K5子式图G,点集I是G的独立集,且I中任意两点的距离至少为3。如果我们给图G中的每个点分配列表L,使得对于u∈I,满足|L(v)| ≥ 3;对于 v∈ V(G)\I,满足|L(v)|≥4,且 L 满足 |L(x)∩L(y)|≤1,那么G是L-可染的。对于不含K3,3子式图,我们获得了类似的结果。图G中最大团的顶点数称为团数,记为w(G)。图G的独立数是指图中最大点独立集里的顶点个数,记为α(G),令G[H]表示点集H在图G中的导出子图。1968年Erd?s和Lovász猜想:如果一个图G的点色数为s+t-1且满足点色数严格大于团数,其中s,t为大于1的整数,那么G的顶点集可以划分成点子集S和T,即V(G)=S∪T,S ∩ T=?,使得χ(G[S])≥s且 χ(G[T])≥t。当(s,t)∈{(2,2),(2,3),(2,4),(3,3),(3,4),(3,5)}时,已被证明此猜想是成立的。2008年,Kostochka和Stiebitz证明了此猜想对于多重图的线图是成立的。2009 年,Balogh,Kostochka,Prince 和 Stiebitz 证明了此猜想对于拟线图和独立数为2的图成立。2019年,Song证明了此猜想对于独立数大于2且不含长度从2到2α(G)-1的洞的图是成立的。本论文研究了如下问题:对点色数为s+t-1且满足点色数严格大于团数的图G,是否可以把G的顶点集划分成点子集S和T,使得χ(G[S])≥s且χ(G[T])≥t+l的问题,并获得了如下两个结果:(1)令s,t,l为满足不等式t≥ s ≥ 3.5l+2的任意正整数。如果多重图G的线图L(G)满足χ(L(G))=s+t-1>ω(L(G)),那么存在一个子图Q为Ks且χ(L(G)-Q)≥t+l。特别地,当l=1时,s,t只要满足大于等于4即可。(2)令s,t为满足t≥s≥4的整数。如果独立数为2的图G满足χ(G)=s+t-1>w(G)+1,那么G的顶点集可以划分成点子集S和T,使得χ(G[S])≥s且χ(G[T])≥t+1。
其他文献
单晶光纤作为一种新型的功能晶体材料,兼具体块单晶与光纤材料的优势,具有物理化学性质稳定、光学质量高、掺杂浓度高、耐高温、抗氧化、比表面积大等优点,在光纤激光以及温度传感等领域具有巨大的应用前景。近年来,关于单晶光纤的研究呈现出火热的态势,包括单晶光纤生长、包层制备技术以及器件开发等方面都在不断突破。相比于国际先进研究水平,我国对于单晶光纤的研究起步较晚,仍处于探索阶段,因此开展高质量单晶光纤的制备
学位
裸甲藻亚胺毒素(Gymnodimines,GYMs)属于环亚胺类毒素(Cyclic imines,CIs),是一种由甲藻产生、广泛分布的海洋生物毒素。GYMs毒性强,有“快速作用”特征,可通过食物链或气溶胶进入生物体,对人类健康和水产养殖造成巨大危害。目前已开发的检测方法有小鼠生物法、液相色谱串联质谱法和受体结合法等,这些方法费用昂贵、操作复杂、特异性低,急需一种特异、灵敏、高效的检测方法。核酸适
学位
自从铅系有机-无机杂化钙钛矿被报道以来,ABX3型有机-无机杂化钙钛矿(A=甲胺、甲脒、铯;B=铅或锡;X=氯、溴、碘或混卤)在光电转换领域的应用已经引进了全世界科学家的广泛关注。但是铅系钙钛中的铅元素对环境有毒性,而锡系钙钛矿中Sn2+相对不够稳定,所以它们的商业化应用进展缓慢。为了解决铅系和锡系钙钛矿的本质缺点,低毒且更稳定的非铅钙钛矿的研究也越来越多,其中以铋系、锑系最为代表。又因Bi3+与
学位
中国正按照“规范、透明、开放、有活力、有韧性”的总目标深化资本市场改革,其中健全信息披露机制与完善投资者保护是重要的推进方向。在新发展阶段,资本市场有效发挥市场化资源配置功能和健全完善激励约束机制的使命与职责,离不开完善的信息机制和畅通的信息渠道。长期以来,我国资本市场参与者之间存在较为严重的信息不对称,导致一系列资源错配问题。管理层、大股东等内部人借助信息优势侵占公司利益的事件频频发生,进一步扭
学位
本文主要研究图的点染色和全染色问题,确切地说,是探究平面图的可松弛性和不含K5子式图的全染色。图G的k-全染色是指用k种颜色对V(G)∪E(G)中的每个元素染色使得任意两个有邻接或关联关系的元素染不同的颜色。而G的全色数χ"(G)则被定义为最小的正整数k使得G有一个k-全染色。Behzad和Vizing独立地提出了著名的全染色猜想:对任意最大度为Δ的图G,都有Δ+1≤χ"(G)≤ Δ+2。下界显然
学位
2007年至2009年的全球金融危机体现了世界金融体系的错综复杂性和巨大的系统性风险,也使得奈特不确定性再度引起了学者的关注。彭实戈院士于2006年所创立的非线性期望理论是处理金融中带有奈特不确定性问题的一个强有力的工具。与Kolmogorov所建立的以线性概率测度为基础的现代概率论公理体系不同,该理论是以非线性期望为出发点,系统建立起的一套全新理论体系,并且该新理论处处都直接对应着概率模型本身的
学位
宽带隙材料具有独特的物理化学性质,在功率电子器件、光学透镜、微波功率器件、机电耦合系统等领域具有广泛应用前景,是开发新一代国防军事、电子通讯、量子技术、医疗健康技术不可或缺的重要材料。宽禁带材料与传统的金属和窄带隙半导体材料(如:硅材料及大部分二维半导体材料)比较,其表面也往往缺乏足够的自由载流子,表现出很大程度的化学惰性,这给利用传统技术手段进行材料表面的加工、改性及结构制作带来了一定的困难,严
学位
MXene是一类性能优异,家族庞大的新型二维晶体材料,因其独特的二维层状结构,以及不同终端官能团展现出的可调谐的性质,引起研究者的广泛关注,在储能、传感、催化等领域具有良好的应用前景。随着研究的深入,MXene面临的问题便凸显出来。目前,MXene的主要合成方法为酸性含氟试剂刻蚀法,导致MXene表面含有大量的F终端基团,终端官能团比较单一,限制了性能的多样性;F终端MXene的稳定性差,极易被氧
学位
聚合算子(也称聚合函数)是用来模拟信息融合的数学模型.近几十年来,随着计算机科学的发展,信息聚合的研究已成为热门研究领域,也是人工智能领域的关键问题之一.目前,聚合算子理论已经广泛应用于模糊逻辑、近似推理、决策、模式识别、图像处理等领域.为了满足不同领域的应用需求,研究学者构造了许多种类型的聚合算子.按其行为、功能的不同,将聚合算子分为四类:合取型聚合算子(以三角模为代表)、析取型聚合算子(以三角
学位
本篇论文主要研究了带延迟的随机最优控制问题和随机斯塔克尔伯格微分博弈问题。我们建立了一般最大值原理、最大值原理与动态规划原理之间的关系、验证定理,得到了反馈控制、开环策略,讨论了闭环可解性。我们还将这些理论结果应用于实际问题,如最优投资问题、生产消费问题、资源分配问题等。经济金融、航空航天、网络通信等领域的许多问题都可以转化为最优控制问题,然而,现实世界中某些现象的发展不仅仅依赖于当前时刻的状态,
学位