不含4,5,7,8--圈的符号图3染色

来源 :华中师范大学 | 被引量 : 0次 | 上传用户:arthurpzl
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文中考虑到的图均为有限,简单图。令图G=(V(G),E(G))且满足映射σ:E(G)→{1,-1}的有序对(G,σ),那么称有序对(G,σ)为符号图,其中σ称为图G的特征。设e为图G中的一条边,那么当σ(e)=1(或σ(e)=-1)时边e为正边(或负边)。(G,σ)是k-着色是指当k为偶数时,V(G)→{±1,±2,…,±k/2};当k为奇数时,V(G)→{0,±1,…,±k-1/2},并且对任意一条边e=uv∈E(G)都有c(u)≠σ(uυ)c(υ)。称图(G,σ)是k-可染的如果它存在一个k-着色。  图的染色问题的研究始于著名的“四色猜想”,但该定理至今无人用纯数学方法证出,因此有许多专家为了寻找一种数学证明方法开始对平面图的3染色问题进行研究。平面图的3染色问题最早的研究是在1959年,Gr(o)tzsch证明了每一个不含三角形的平面图是3-可染的。随后在1976年Steinberg提出了一个猜想:每个不含4,5-圈的平面图都是3-可染的。但在2017年Cohen-Addad,Hebdige,Král, Li和Salgado证明了Steinberg猜想是不成立的。因此对于符号图而言Steinberg猜想同样是不成立的,但问题同样存在。目前对符号图的染色问题已有很多,本文在其基础上证明了不含4,5,7,8-圈的符号图是3-可染的。  第一章介绍了本文的研究背景、最新进展及本文所解决的问题。  第二章介绍了本文涉及到的基本概念及符号。  第三章给出了本文的可约结构及其证明。  第四章给出了本文的权转移规则及通过权转移后图G的最终点、面权值。
其他文献
信息与算法的复杂性(Information Based Complexity)是计算数学最主要的研究方向之一.在研究多变量函数的数值问题时,当自变量的个数d非常大时,几乎不可能用解析的方法来处理.
本文研究一个可穿透障碍物和一个不可穿透障碍物混合的声波散射问题.假设D1(∈)R2是一个有界区域,具有光滑边界,且为一个可穿透障碍物,D2(∈) R2也是一个有界区域,具有Lipschitz
本论文综合利用了群论和图论的知识,提出了交换图和整除图的概念,并研究其图论性质和群论性质。  第一章,简单介绍了本文的研究背景,给出了一些常用概念及其表示符号,并且
设K是一个特征为零的代数闭域,V是域K上有限维非零向量空间.所谓V上的一个勒纳德对是指由End(V)中的两个线性变换A和A*构成的有序对,并且满足对于任意的其中一个B,都存在V的一组
具有血缘、姻缘及收养关系的成员共居和生活在一起组成家庭户,主要包括单人户、核心家庭、夫妻家庭、直系家庭、联合家庭等户类型,不同区域家庭结构存在差异,婚姻、生育、死亡、
西藏生物影像调查(TBIS)  在离天空最近的高原地区,有巍峨的雪山、壮丽的冰川,也有为这片土地带来无限生机的高山花卉。高山花卉通常生长在海拔3000米以上。杜鹃、报春和龙胆是世界公认的三大高山花卉,而在中国,由于喜马拉雅山脉和横断山脉得天独厚的存在,高山花卉的队伍中新增了绿绒蒿,形成了四大高山花卉。由于高山上紫外线强烈,高山植物会产生大量的胡萝卜素和花青素来防止紫外线过强的危害,因此高山花卉往往
自从首次提出混沌的概念,混沌就成为拓扑动力系统的重要研究内容.根据不同的判定规则,人们给出了不同的混沌概念并进行深入研究,Li-Yorke混沌,分布混沌,按序列分布混沌,Devaney混沌
三年一届的世界工程机械展会——法国INTERMAT展于2009年4月25日在巴黎VILLEPAINT国际展览中心如期闭幕。山河智能在此次国内外工程机械巨头同台竞技的顶尖级盛会上大放异彩
本文介绍了带可乘白噪音和div(σ(x)▽u)项的半线性退化抛物方程,主要研究它的唯一解所确定的随机动力系统在L2空间中的有界域上是否存在随机吸引子的问题.本文考虑如下带可乘
为了打击盗版,维护多媒体文件生产商的合法权益,Trappe等人于2002年提出了t-抗合谋攻击码(t-ResilientAnti-CollusionCode,简记为t-ACC),并针对倍受盗版者青睐的平均攻击,引入了t-