符号图的边染色和全染色问题研究

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:liyuwei9999
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
令G=(V,E)是一个无环的图,其中V表示点集,E表示边集.符号图Γ=(G,σ)是指在图G的基础上给其边集加一个符号映射σ:E(G)→{+1,-1},使得G的每一条边e都有一个符号σe,称G为符号图Γ=(G,σ)的底图.若σe=1,则e是正边;若σe=-1,则e是负边.一个incidence表示为点-边序对(v,e),其中v∈V(Γ),e ∈E(Γ),v是e的一个端点.用I(r)表示符号图Γ中incidence的集合.若k=2q(若k=2q+1),符号图r=(G,σ)的一个k-边染色是指存在一个映射f:I(r)→{±1,±2,…,±q}(相应地,f:I(r)→{0,±1,±2,…,±q}),使得对任意的边e=xy∈ E(Γ)都有f(x,e)=-σef(y,e).如果对任意相邻的两条边e1=xy和e2=xz使得f(z,e1)≠f(x,e2),则称f是Γ=(G,σ)上的正常k-边染色.如果符号图r=(G,σ)有一个正常k-边染色,称r是k-边可染的.记符号图r的边色数为χ’(Γ),定义为使得r是k-边可染的最小正整数k的值.该定义由Behr在2020年提出,可以看出当符号图Γ中的边均为负边时,该定义为图G的正常边染色.此外,Behr在简单符号图r=(G,σ)中证明了 Vizing定理,即△(r)≤χ’(r)≤△(r)+1.本文研究当符号图r=(G,σ)有重边时边色数的上界.本文中还将研究符号图Γ=(G,σ)的点-边全染色.图G的一个正常k-全染色是指一个映射f:V(G)∪E(G)→{1,2,…,k},使得任意两个相邻点,相邻边,相关联的点和边均染不同色.如果图G有一个正常k-全染色,称G是kk-全可染的.记G的全色数为χ"(G),定义为使得G是k-全可染的最小正整数k的值.关于全色数的上界,Vizing和Bchzad分别独立地提出著名的全染色猜想:对任意的简单图G,χ"(G)≤ △(G)+2.全染色猜想引起广大学者的研究兴趣.本文将在符号图r=(G,σ)中研究点-边全染色,给出符号图中点-边全染色的定义,在某些符号图类中考虑全色数的上界.本文主要围绕符号图展开研究,先后考虑符号图的边染色,符号图的全染色.学位论文分为以下章节:第一章节,首先介绍论文中常用的基本定义符号以及相关问题的研究现状,最后陈述获得的主要结果.第二章节和第三章节,分别研究当符号图有重边时边色数的上界,某些符号图全色数的上界.具体来讲,我们运用数学归纳法,色延拓技巧,颜色变换等方法证明了如下结果:(1)若符号图r=(G,σ)是多重图,当r不含有μ(r)-三角形,χ’(r)≤△(r)+μ(r).需指出:该结果考虑的是非0染色.(2)若r=(G,σ)是最大度为3的符号图,则χ"(r)≤5.(3)若符号图是树Tn,则χ"(Tn)=Δ(Tn)+1.(4)若符号图是完全图Kn,则
其他文献
圩区圩田系统是苏皖地区人地和谐相处的智慧结晶,人类聚居其中,沿水筑堤,圩堤顺水势线型生长,村屋沿堤集聚,在其历史进程中,自然而然形成了形态特殊的线型村落。这些村落受到圩堤、圩田的影响,线型发展、生长、演变,其本身具有一定的地域特殊性、生态脆弱性以及空间特殊性。现如今圩区系统水网破坏、洪涝灾害以及水体污染等问题开始显现;青壮人口流失,文化失落,标签化改造正逐步侵蚀着圩田圩区系统,千村一面的样板化改造
图的分解是将一个图划分成一组边不相交的子图.图G的荫度是指G边分解所需e(H)的最少森林数.图G的分数荫度定义为γf(G)=maxH(?)G,v(H)1e(H)/v(H)-1.1986年,Payan最早介绍了这个概念.而著名的Nash-Williams定理提出并证明了一个图G可分解为至多k个森林的充分必要条件.1961年,Nash-Williams和Tutte独立证明了一个图G包含k个边不相交的支
分段微分系统的研究是近年的热点课题之一.本文考虑一类分段光滑近哈密顿系统,应用首阶Melnikov函数方法,给出了系统分别在一次、二次、三次和四次多项式扰动下产生的极限环个数.具体的研究过程分为以下四章:第一章简要介绍了常微分与动力系统的发展概况,分段光滑哈密顿系统的研究现状以及主要结论.第二章作为本文的重要组成部分之一,首先对所研究的系统进行分析,明确本文的研究对象;其次给出了系统的首阶Meln
地表反照率是表征地表对于太阳辐射反射能力强弱的物理量;定义为地表反射的太阳辐射通量与入射太阳辐射通量的比值。高分辨率地表反照率遥感产品以其空间分辨率高的优点,目前正成为区域能量平衡和气候变化研究的重要数据源。目前地表反照率反演方法主要有窄波段向宽波段转换、基于多时相遥感观测数据的BRDF建模以及直接反演算法等,这些算法难以同时兼顾高时间和高空间分辨率,且现行的高分辨率地表反照率遥感反演算法及数据产
前列腺癌(Prostate cancer,PC)是男性泌尿生殖系统最常见的恶性肿瘤,患者在接受雄激素剥夺疗法(Androgen deprivation therapy,ADT)后,病情往往会继续发展至去势抵抗性阶段,危及生命。抗雄激素药物是目前治疗去势抵抗性前列腺癌(Castration-Resistant prostate cancer,CRPC)最重要且有效的方法。但是用药一段时间后,患者大多
本文以长江河口水下三角洲A3-1和A6-6柱样为对象,在高精度年代框架的基础上,结合环境磁学、粒度、漫反射光谱、地球化学测量等手段,查明了长江口水下三角洲两个沉积区域的柱样沉积物的磁性特征,揭示了粒度、早期成岩改造作用和物源变化等因素对长江口水下三角洲沉积物磁性特征的影响,探讨了长江口水下三角洲沉积物物质组成差异及其源汇过程,并提取环境变化的信息。结果表明:(1)光释光(OSL)测年结果表明,位于
令G是一个图.分别用V(G),E(G)和F(G)表示G的顶点集,边集以及面集,简记为V,E和F.给定两个非负整数s,t,若存在映射π:E(G)→{1,2,…,k使得G中任意一条边e,满足其颜色π(e)在它的1-邻域中至多出现s次,且在它的2-邻域中至多出现t次.则称π是G的一个(s,t)-松弛强边k-染色,并称G是(s,t)-松弛强边k-可染的.这里e的1-邻域是指它的邻边,e的2-邻域边是指与e
太阳光驱动水蒸发是净化水的一种简单而绿色的方法,然而利用太阳光驱动水蒸发的效率相当低,需要昂贵的光学聚焦系统提升其光热转化效率。最近,纳米材料使这项技术变成了现实,使其能够在普通环境中利用太阳光将吸光体局部加热,从而使水快速蒸发。利用纳米材料使太阳光驱动水蒸发,无需额外能量输入即可实现高效水蒸发,具有热损小、转化率高、结构灵活等特点,存在大规模应用地潜能。本论文成功制备了还原石墨烯海藻酸钙凝胶膜,
队列是计算机科学里最基本的数据结构,Heath,Leighton和Rosenberg在1992年最先提出队列问题在图论上的表述方式,并定义了图的队列数.随后在2005年,Wood给出了严格队列数的概念.彩虹和弱彩虹分别是队列和严格队列的对偶概念,它们之间有着非常紧密的联系.Wood在2005年将强积结构应用到了队列数上.对于k次方图,Wood在2005年给出了路和圈k次方图的队列数和严格队列数的上
Finsler几何是一类不具有二次型限制的黎曼几何.在欧氏空间开域上的典范Finsler度量为Finsler几何研究提供了重要的例子和几何性质,包括球对称Finsler度量、射影平坦Finsler度量、对偶平坦Finsler度量以及具有各种曲率性质的Finsler度量等等.根据对偶平坦方程和射影平坦方程的线性结构,众多Finsler几何学家通过研究已知的Finsler度量和解析方法,发掘出了更多非