严政，赵小鹏，慈永鑫

长江大学信息与数学学院，湖北 荆州 434023

1 基本结果

关于图G的无矛盾染色，CZAP等[2]首先确定了路径的无矛盾连通数。

命题1[2]设Pn表示有n条边的路径，则：

设C(G)是G中由割边诱导的子图，用Q1,Q2,…,Ql表示C(G)的分支，记h(G)=max{cfc(Qi):Qi是C(G)中的分支}。

命题2[2]设G是一个有割边的连通图，则：

h(G)≤cfc(G)≤h(G)+1

对于阶为n的连通图G，1≤cfc(G)≤n-1；当且仅当G=Kn时，cfc(G)=1；当且仅当G=K1,n-1时，cfc(G)=n-1[3，5，10]。若G是非完全图，则cfc(G)≥2。特别地，对于2-连通图，cfc(G)=2；文献[3，11]进一步得到，对于非完全2-边连通图，cfc(G)=2。

命题3[2]设G是一个非完全2-连通图，则cfc(G)=2。

设t是正整数，G的t-冠(corona)是指向G的每个顶点添加t条悬挂边所构成的图。

命题4[2]设Cn=v1v2,…,vn(n≥4)是一个圈，G是它的2-冠，则cfc(G)=3。

命题5[2]设G是一个有割边的连通图，则cfc(G)≤max{2，|E(C(G))|}。

引理1[2]设G是一个连通图，则从G的每一个非平凡块中适当选择一条边，可形成G的一个匹配。

引理2[2]设G是一个2-连通图，e∈E(G)，则G中任意2个不同的顶点u和v之间存在1条包含e的u-v路径。

关于无矛盾连通数的更多结论,详见文献[3]和[10,11]。

2 主要结果

2.1 阶小于ks+2s+3k+6(s≥k≥2)的连通图的无矛盾连通数

定理1设G是一个阶为n(n≥2)的连通图，其中n≤ks+2s+3k+5(s≥k≥2)。如果δ(G)≥s+2，则cfc(G)≤k。

证明先用反证法证明G至多有k条割边。假设G有l(l≥k+1)条割边，则删除G的所有割边得到l+1个连通分支，设H0是其中最小的分支。

情形1|V(H0)|=a≤s+2。

由于δ(G)≥s+2，所以H0中的每一个顶点都至少连接一条割边。设y为G中与H0关联的割边数，则：

整理得：

a(s+2)≤a(a-1)+y

即：

y≥a(s-a+3)

又：

a(s-a+3)-(s+2)=a(s+2+1-a)-(s+2)

=(s+2)(a-1)+a(1-a)

=(a-1)(s+2-a)≥0

因此，y≥s+2≥k+2。设G中与H0相关联的割边分别为e1,e2,…,ey，则G={e1,e2,…,ey}有y+1个连通分支，记为H0,H1,…,Hy。因为δ(G)≥s+2≥4，所以对于任意的Hi(1≤i≤y)，都存在v∈V(Hi)，使得N(v)⊆V(Hi)，从而每个Hi至少有δ(G)+1个顶点。于是：

≥y(s+3)

≥(k+2)(s+3)

=ks+2s+3k+6

与n≤ks+2s+3k+5矛盾。

情形2|V(H0)|≥s+3。

由δ(G)≥s+2，得：

≥(l+1)(s+3)

≥(k+2)(s+3)

=ks+2s+3k+6

这与n≤ks+2s+3k+5矛盾。

因此G至多有k条割边。由命题5可知，当k≥2时，cfc(G)≤k。

定理1中的界是紧的。构造图Gk+1如下：记H0,H1,…,Hk+1均是阶为s+2的完全图，取H0中任意一点分别与H1,H2,…,Hk+1中的一点连接。……