论文部分内容阅读
整数流的概念是Tutte在解决四色猜想时引入的.设D(G)是图G的一个定向,ED+(v)和ED-(v)分别表示以u为起点和终点的所有边的集合.若存在映射f:E(G)→(±1,±2,…,±(k-1)}使得对任意点u∈V(G)都有则称图G存在处处非零k-流.1976年,Tutte提出3-流猜想：每个4-边连通图存在处处非零3-流.1992年,Jaeger等人[21]把整数流的概念成功推广为群连通的概念.设A是一个Abel加群,其单位元为0.若对任意满足∑v∈V(G)b(u)=0的b:V(G)→A,存在映射f:E(G)→A-{0}使得对任意点u∈V(G)都有则称G是A-连通的.设Z3表示阶为3的循环群.Jaeger等人在文献[21]中猜想：每个5-边连通图是Z3-连通的.设d1,d2,…,dk是k个非负的整数,如果图G的点集可以划分成k个集合V1,V2,…,Vk,使得对于i=1,2,…,k,都有子图G[Vi]的最大度至多为di,则称图G是非正常(d1,d2,…,dk)-可着色的(简称为(d1,d2,…,dk)-可着色的).2003年,Borodin和Respaud[6]提出了著名的Bordeaux猜想：每个满足三角形距离至少为1(即d▽≥1)并且不含5-圈的平面图是3-可着色的.围绕上面的三个猜想,本文主要作了下面的研究.首先,我们研究了无爪图的处处非零3-流.定义N1,1,0是由3-圈u1u2u3u1添加两个不同的点v1,u2以及两条边u1u1,u2u2所得到的图.若图G*是通过不断收缩图G的非平凡的A-连通子图直到没有这样的图存在为止所得到的图,则称G可A-收缩到图G*.我们证明了对于一个{N1,1,0,claw}-free,2-连通简单图G,如果图G不存在处处非零3-流当且仅当G能Z3-收缩为y中的一个图,或者G是图2-4中的G1,G2,G3,G4,G5的一个,或者G∈H.其次,我们研究了不含长度至少为5的诱导圈的无爪图的Z3-连通性.设G是一个4-边连通的无爪图,如果G中不含长度至少为5的诱导圈,则G是Z3-连通的.最后,我们研究了既不含6-圈又没有近距离的三角形的平面图的非正常着色.众所周知,确定一个平面图是否是3-可着色是NP-困难的,为了讨论平面图的3-可着色问题,经典的着色被推广到非正常着色.我们证明了对于一个不含6-圈的平面图G,如果G中三角形的距离至少为1,则G是(1,1,1)-可着色的.