科研之友
微信
新浪微博
Facebook
分享链接
摘要
称一个图中长度至少为4的导出圈为该图的洞,长度为奇数和偶数的洞分别被称为奇洞和偶洞.由Petersen图去掉一条2长路的顶点所得到的图记为θ-,由Petersen图去掉一对相邻顶点所得到的图记为θ+,由θ+去掉一条关联两个3度顶点的边所得到的图记为θ.设l≥2为整数且令r=min{l-1,[l/2]+1},Gl表示围长为2l+1且不含其他长度奇洞的图类,G∈Gl,u∈V(G),S?V(G)是一个非空子集.用G[S]表示由S导出的子图,定义d(u,S)=min{d(u,v):v∈S},并定义Li(S)={u∈V(G)且d(u,S)=i}.本文证明了,如果G[S]连通且对于每一个整数i∈{1,…,r}而言G[Li(S)]都是二部图,则对于所有整数i>0,G[Li(S)]都是二部图,从而χ(G)≤4.本文还证明了,若非Petersen图G∈G2 3-连通且所有3-顶点割集都是独立集,则G有导出子图θ或者θ-但没有导出子图θ+.作为其推论,若图G∈G2的导出子图中既没有θ又没有θ-,则χ(G)≤3,并且G2中极小非3-可染色图一定不包含θ+为导出子图.
- 单位
