论文部分内容阅读
本文中考虑到的图均为有限,简单图。令图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的最终点、面权值。