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