文献[1-2],文献[3-5]和文献[6-9]分别研究点可区别正常边染色、一般边染色以及正常全染色.文献[10]中讨论两类点可区别的未必正常的全染色:点可区别Ⅰ-全染色和点可区别Ⅵ-全染色.文献[11]中讨论了图的几类未必正常的全染色的邻点可区别性.

所谓图G的一般全染色是指若干种颜色对于图G的点及边的一个分配^[10-11].

对于图G的一个一般全染色,如果任意两个相邻点染以不同颜色,并且任意两条相邻边染以不同颜色,那么称它为图G的Ⅰ-全染色^[10-11].

对于图G的一个一般全染色,如果任意两条相邻边染以不同颜色,那么称它为图G的Ⅵ-全染色^[10-11].

对图G的任意一个Ⅰ-全染色或Ⅵ-全染色f以及G的任意一个顶点u,用C_f(u)或C(u)表示在f下点u的颜色以及与u关联的所有边的颜色构成的集合,即C(u)={f(uv)|uv∈E}∪{f(u)}.注意C(u)不是多重集,显然有|C(u)|≤d_G(u)+1.令C(u)^-表示C(u)在全体颜色构成的集合中的补集.

如果f是图G的使用颜色1,2,…,k的一个Ⅰ-全染色(或者Ⅵ-全染色),并且u,v∈V(G),u≠v,有C(u)≠C(v),则称f为G的k-点可区别Ⅰ-全染色(或者k-点可区别Ⅵ-全染色),或k-Vertex-distinguishing Ⅰ-total colorings(或者k-Vertex-distinguishing Ⅵ-total colorings).图G的点可区别Ⅰ-全染色(或者点可区别Ⅵ-全染色)所需颜色的最少数目,称为G的点可区别Ⅰ-全色数(或者点可区别Ⅵ-全色数),记为χⁱ_vt(G)(或者χ^vi_vt(G)),即χⁱ_vt(G)=min{k|G有k-VDIT染色}(或者χ^vi_vt (G)=min{k|G有k-VDVIT染色}).

两个不相交的图的联图是指将一个图G(V₁,E₁)的每个顶点与另一个图H(V₂,E₂)的每个顶点相连接起来所得到的图,记作G∨H(V,E),其中V=V₁∪V₂,E=E₁∪E₂∪{uv|u∈V₁,v∈V₂}.

文献[10]讨论了完全图、完全二部图、扇、轮、双星、路、圈、两个阶相同的圈的联、阶n为偶数的完全图去掉(n)/4 条能构成为一个匹配的边后所得图的点可区别Ⅰ-全染色和点可区别VI-全染色,并提出了如下VDITC(vertex-distinguishing Ⅰ-total colorings)猜想和VDVITC(vertex-distinguishing Ⅵ-total colorings)猜想.

对于图G,令n_i表示度为i的顶点的数目,δ≤i≤Δ,假设ζ(G)=min{l|(l

i)+(l

i+1)+(l

i+2)+…+(l

i+s)+(l

i+s+1)≥n_i+n_i+1+n_i+2+…+n_i+s,δ≤i≤i+s≤Δ,s≥0}.

猜想1^[10](VDITC猜想)χⁱ_vt(G)=ζ(G)(或ζ(G)+1).

猜想2^[10](VDVITC猜想)χ^vi_vt(G)=ζ(G)(或ζ(G)+1).

引理1^[10] χⁱ_vt(G)≥χ^vi_vt(G)≥ζ(G).

引理2(i)χⁱ_vt(G)≥χ^vi_vt(G)≥Δ(G),

(ii)对于任意图G,如果存在至少两个Δ-顶点,则χⁱ_vt(G)≥χ^vi_vt(G)≥Δ+1.

证明 如果图G存在两个Δ-顶点且只使用Δ种颜色对图G进行Ⅵ-全染色,此时两个最大度点的色集合相同使得这两个最大度点无法区分,故χ^vi_vt(G)≥Δ+1.

引理3^[10] 如果存在正整数r,δ≤r≤Δ,且G没有度为r的顶点,则

ζ(G)=min{l|(l

i)+(l

i+1)+…+(l

i+s)+

(l

i+s+1)≥n_i+n_i+1+…+n_i+s,δ≤i≤i+

s≤r-1,s≥0; 或r+1≤i≤i+s≤Δ,s≥0}.

引理4 若图G存在至少两个Δ-顶点,且χⁱ_vt(G)=Δ+1,则χ^vi_vt(G)=χⁱ_vt(G)=Δ(G)+1.

引理5 若图G只有一个Δ-顶点,且χⁱ_vt(G)=Δ,则χ^vi_vt(G)=χⁱ_vt(G)=Δ(G).

命题1^[10] 当n≥4时,有

χⁱ_vt(C_n∨C_n)=χ^vi_vt(C_n∨C_n)=n+4.

假设p∈Z,而q为正整数,本文中用(p)_q表示{1,2,…,q}中的模q同余于p的那个数,即(p)_q∈{1,2,…,q}且(p)_q≡p(mod q).

在文献[8]和文献[9]中分别讨论了C_m∨C_n和C_m∨F_n的点可区别全染色.在本文中主要讨论圈与圈的联C_m∨C_n(m≠n),圈与轮的联C_m∨W_n以及圈与扇的联C_m∨F_n的点可区别Ⅰ-(Ⅵ-)全染色,并证明VDITC猜想和VDVITC猜想对!![C_m∨C_n,C_m∨W_n,C_m∨F_n]是成立的.

定理1 设C_m∨C_n是两个圈的联,且 n>m≥3,则χⁱ_vt(C_m∨C_n)=n+3.

证明 令V(C_m∨C_n)={u₁,…,u_m,v₁,…,v_n},E(C_m∨C_n)={u₁u₂,u₂u₃,…,u_m-1u_m,u_mu₁,v₁v₂,v₂v₃,…,v_n-1v_n,v_nv₁}∪{u_iv_j|i=1,2,…,m; j=1,2,…,n}.

经计算得ζ(C_m∨C_n)=min{l|(l

n+2)+(l

n+3)≥m,(l

m+2)+(l

m+3)≥n}=n+3,所以由引理1得χⁱ_vt(C_m∨C_n)≥n+3.现在只需证明C_m∨C_n有一个(n+3)-VDIT染色f.有以下两种情形需要考虑.

情形1:m≡0(mod2)

第1步:先给连接u_i与v_j的边进行染色,令

f(u_iv_j)=(i+j-1)_n+1,f(u_iv_j)∈{1,2,…,n+

1},1≤i≤m,1≤j≤n.

第2步:再给两个圈的边进行染色,令

f(v_jv_j+1)=n+2,j∈{2,…,n-1},且j是奇数;

f(v_jv_j+1)=n+3,j∈{2,…,n-1},且j是偶数;

当n为奇数时,f(v_nv₁)=n+2;

当n为偶数时,f(v_nv₁)=n+3; f(v₁v₂)=n+1.

f(u_iu_i+1)=n+2,i∈{1,2,…,m-1},且i是奇数;

f(u_iu_i+1)=n+3,i∈{1,2,…,m-1},且i是偶数;

f(u_mu₁)=n+3.

第3步:最后给点染色,令

f(u_i)=i,f(u_i)∈{1,…,m},1≤i≤m.

对C_n的点进行染色时不要用{1,…,m}中的颜色.

f(v_j)=n+2,j∈{2,…,n},且j是奇数;

f(v_j)=n+3,j∈{2,…,n},且j是偶数;

f(v₁)=n+1.

上述染色是Ⅰ-全染色,并且在此染色下有

C(u_i)={i,i+1,i+2,…,(i+n-1)_n+1,n+2,

n+3},1≤i≤m;

C(v_j)={j,j+1,(j+2)_n+1,…,(j+m-1)_n+1,

n+2,n+3},j≠1,2;

C(v₂)={2,3,…,m+1,n+1,n+3}; 当n为奇数时,

C(v₁)={1,2,3,…,m,n+1,n+2}; 当n为偶数时,

C(v₁)={1,2,3,…,m,n+1,n+3}.

C(u_i)^-={(i-1)_n+1},i∈{1,2,…,m}.

可见m+n个点的色集合彼此互异,故上述Ⅰ-全染色是点可区别的.

情形2:m≡1(mod2)

第1步:先给连接u_i与v_j的边进行染色,令

f(u_iv_j)=(i+j-1)_n+1,f(u_iv_j)∈{1,2,…,n+1},1≤i≤m-1,1≤j≤n; f(u_mv_j)=(i+j+2)_n+2,1≤j≤n.

第2步:再给两个圈的边进行染色,令

f(u_iu_i+1)=n+2,i∈{1,2,…,m-1},且i是奇数; f(u_iu_i+1)=n+3,i∈{1,2,…,m-1},且i是偶数; f(u_mu₁)=n+1.

f(v_nv₁)=n+3,f(v₁v₂)=n+1.

当n为奇数时,f(v_jv_j+1)=n+3,j∈{2,…,n-1},且j是奇数; f(v_jv_j+1)=n+2,j∈{2,…,n-1},且j是偶数.

当n为偶数时,f(v_jv_j+1)=n+2,j∈{2,…,n-1},且j是奇数; f(v_jv_j+1)=n+3,j∈{2,…,n-1},且j是偶数; f(v_nv₁)=n+3.

第3步:最后给点染色,令

f(u_i)=i,f(u_i)∈{1,…,m},1≤i≤m; f(v₁)=n+1.

当n为奇数时,f(v_j)=n+3,j∈{2,…,n},且j是奇数; f(v_j)=n+2,j∈{2,…,n},且j是偶数.

当n为偶数时,f(v_j)=n+2,j∈{2,…,n},且j是奇数; f(v_j)=n+3,j∈{2,…,n},且j是偶数.

上述染色是Ⅰ-全染色,并且在此染色下有

C(u_i)={i,i+1,i+2,…,(i+n-1)_n+1,n+2,n+3},i≠1,m;

C(u₁)={1,2,…,n,n+1,n+2},C(u_m)={1,2,…,n-1,n+1,n+2,n+3};

C(v_j)={j,j+1,(j+2)_n+1,…,(j+m-2)_n+1,j-1,n+2,n+3},j≠1,2;

C(v₁)={1,2,…,m-1,n+1,n+2,n+3}.

当n为奇数时,C(v₂)={1,2,…,m,n+1,n+2}; 当n为偶数时,C(v₂)={1,2,…,m,n+1,n+3}.

C(u_i)^-={i-1},i≠1,m;

C(u₁)^-={n+3},C(u_m)^-={n}.

可见m+n个点的色集合彼此互异,故上述Ⅰ-全染色是点可区别的.

因此,不管哪种情形所得到的染色f都是C_m∨C_n的一个VDIT染色.

定理2 设C_m∨W_n是圈和轮的联图,且 n≥3,m≥3,则χⁱ_vt(C_m∨W_n)={m+4,n=3,m≥3;

n+4,m=3,n≥4;

m+n,m≥4,n≥4.

证明 令V(C_m∨W_n)={u₁,…,u_m,v₀,v₁,…,v_n},E(C_m∨W_n)={u₁u₂,u₂u₃,…,u_m-1u_m,u_mu₁,v₀v₁,v₀v₂,…,v₀v_n,v₁v₂,v₂v₃,…,v_n-1v_n,v_nv₁}∪{u_iv_j|i=1,2,…,m; j=0,1,2,…,n}.

(i)当n=3,m=3时,C₃∨W₃ 有7个6度(最大度)的点,由引理2(ii)知,χⁱ_vt(C₃∨W₃)≥7,只需给出C₃∨W₃的一个7点可区别Ⅰ-全染色f.令

f(u_iv_j)=i+j,i=1,2,3,j=1,2;

f(u_iv₃)=i,i=1,2,3;

f(u₁v₀)=4,f(u₂v₀)=5,f(u₃v₀)=7,

f(v₁v₀)=1,f(v₂v₀)=2,f(v₃v₀)=6;

f(u₁u₂)=7,f(u₂u₃)=1,f(u₃u₁)=6,

f(v₁v₂)=6,f(v₂v₃)=7,f(v₃v₁)=5;

f(v_j)=j,j=1,2,3; f(v₀)=7;

f(u_i)=3+i,i=1,2,3.

上述染色是Ⅰ-全染色,并且在此染色下有

C(v₀)^-={3},C(v₁)^-={7},C(v₂)^-={1},

C(v₃)^-={4},C(u₁)^-={5},C(u₂)^-={6},

C(u₃)^-={2}.

可见7个点的色集合彼此互异,故上述Ⅰ-全染色是点可区别的.

当n=3,m≥4时,C_m∨W₃有4个m+3度(最大度)的点,由引理2(ii)知,χⁱ_vt(C_m∨W₃)≥m+4,只需给出C_m∨W₃的一个m+4点可区别Ⅰ-全染色f.令

f(u_iv_j)=i+j,1≤i≤m,j=1,2;

f(u_iv₃)=n+i+1,1≤i≤m-1;

f(u_mv₃)=2,f(u_iv₀)=i+3,1≤i≤m.

f(u_iu_i+1)=i,i∈{1,2,…,m-1};

f(u_mu₁)=m+4.

f(v₁v₂)=m+3,f(v₂v₃)=1,

f(v₃v₁)=m+4,f(v₀v_j)=j,j=1,2,3.

f(v_j)=j,j=1,2,3;

f(u_i)=i+3,1≤i≤m; f(v₀)=m+4.

上述染色是Ⅰ-全染色,并且在此染色下有

C(u_i)={i-1,i,…,i+4},i{1,m};

C(u₁)={1,2,…,5,m+4},

C(u_m)={m-1,m+1,m+2,…,m+4,2};

C(v_j)={j,j+1,(j+2)_n+1,…,

(j+m-2)_n+1,j-1,n+2,n+3},j≠1,2;

C(v₁)={1,2,…,m-1,n+1,n+2,n+3}.

C(v₀)^-=,C(v₁)^-={m+2},

C(v₂)^-={m+4},C(v₃)^-={4}.

可见m+4个点的色集合彼此互异,故上述Ⅰ-全染色是点可区别的.

(ii)当m=3,n≥4时,C₃∨W_n 有4个n+3度(最大度)的点,由引理2(ii)知,χⁱ_vt(C₃∨W_n)≥n+4,只需给出C₃∨W_n的一个n+4点可区别Ⅰ-全染色f.

当m=3,n=4时,令

f(u_iv_j)=i+j,j=1,2,3,i=1,2,3.

f(u₁v₄)=6,f(u₂v₄)=7,f(u₃v₄)=1,

f(u₁v₀)=5,f(u₂v₀)=8,f(u₃v₀)=7.

f(v₀v_j)=j,j=1,2,3,4,

f(v₁v₂)=6,f(v₂v₃)=7,

f(v₃v₄)=2,f(v₄v₁)=8.

f(u₁u₂)=1,f(u₂u₃)=2,f(u₃u₁)=8.

f(v_j)=j,j≠3; f(v₃)=1,f(v₀)=6,

f(u₁)=5,f(u₂)=8,f(u₃)=7.

上述染色是Ⅰ-全染色,并且在此染色下有

C(v₁)={1,2,3,4,6,8},

C(v₂)={2,3,4,5,6,7},

C(v₃)={1,2,…,7},C(v₄)={1,2,4,6,7,8};

C(v₀)^-=,C(u₁)^-={7},C(u₂)^-={6},

C(u₃)^-={3}.

可见8个点的色集合彼此互异,故上述Ⅰ-全染色是点可区别的.

当m=3,n≥5时,令

f(u_iv_j)=i+j,1≤j≤n-1,i=1,2,3;

f(u₁v_n)=n+2,f(u₂v_n)=n+3,

f(u₃v_n)=1,f(u_iv₀)=i+n,i=1,2,3,

f(v_jv_j+1)=j+5,j∈{1,2,…,n-2};

f(v_n-1v_n)=2,f(v_nv₁)=n+4,

f(v₀v_j)=j,j=1,2,…,n,

f(u₁u₂)=1,f(u₂u₃)=2,f(u₃u₁)=n+4.

f(v_j)=j,j=1,2,…,n; f(v₀)=n+4,

f(u_i)=n+i,i=1,2,3.

上述染色是Ⅰ-全染色,并且在此染色下有

C(v_j)={j,j+1,…,j+5},j≠1,n-1,n;

C(v₁)={1,2,3,4,6,n+4},

C(v_n-1)={n-1,n,…,n+3,2},

C(v_n)={1,2,n,n+2,n+3,n+4};

C(v₀)^-=,C(u₁)^-={n+3},

C(u₂)^-={n+4},C(u₃)^-={3}.

可见n+4个点的色集合彼此互异,故上述Ⅰ-全染色是点可区别的.

(iii)当m≥4,n≥4,由引理3得ζ(C_m∨W_n)=min{l|(l

m+n)+(l

m+n+1)≥1,(l

m+3)+(l

m+4)≥n,(l

n+3)+(l

n+4)≥m}=m+n,故由引理 1得χⁱ_vt(C_m∨W_n)≥m+n.现只需证明C_m∨W_n有一个(m+n)-VDIT染色f.有两种情形需要考虑.

情形1:n≥m

当m=4,n=4时,令

f(u_iv_j)=i+j,1≤i≤4,1≤j≤3.

f(u_iv₄)=i+5,i≠4; f(u₄v₄)=3.

f(u₁v₀)=7,f(u₂v₀)=6,f(u₃v₀)=3,

f(u₄v₀)=4,f(v₁v₀)=8,f(v₂v₀)=2,

f(v₃v₀)=1,f(v₄v₀)=5;

f(u₁u₂)=8,f(u₂u₃)=1,f(u₃u₄)=2,

f(u₄u₁)=1; f(v₁v₂)=7,f(v₂v₃)=8,

f(v₃v₄)=2,f(v₄v₁)=1.

f(u_i)=f(u_iv₀),

f(v₀)=8,f(v_j)=f(v_jv₀),j≠1; f(v₁)=1.

最终得到的上述全染色是Ⅰ-全染色,并且在此染色下有

C(v₀)^-=,C(u₁)^-={5},C(u₂)^-={2},

C(u₃)^-={7},C(u₄)^-={8},C(v₁)^-={6},

C(v₂)^-={1},C(v₃)^-={3},C(v₄)^-={4}.

可见9个点的色集合彼此互异,故上述Ⅰ-全染色是点可区别的.

当m=4,n≥5时,令

f(u_iv_j)=i+j,i=1,2,3,4,j=1,2,…,n-1.

f(u_iv_n)=n+i+1,i≠4; f(u₄v_n)=2.

f(u_iv₀)=n+i,i≠2; f(u₂v₀)=1.

f(v_jv₀)=j,j≠1; f(v₁v₀)=n+2.

f(u₁u₂)=n+4,f(u₂u₃)=2,f(u₃u₄)=3,

f(u₄u₁)=1.

f(v_jv_j+1)=(j-1)_n+4,j≠n; f(v_nv₁)=1.

f(u_i)=f(u_iv₀),i≠4; f(u₄)=1.

f(v₀)=n+4,f(v_j)=f(v_jv₀).

上述染色是Ⅰ-全染色,并且在此染色下有

C(v_j)={(j-2)_n+4,j-1,j,j+1,j+2,j+3,

j+4},j≠1,n; C(v₁)={1,2,3,4,5,n+2,

n+4},C(v_n)={n-2,n,n+2,n+3,

n+4,1,2}.

C(v₀)^-=,C(u₁)^-={n+3},C(u₂)^-=

{n+2},C(u₃)^-={1},C(u₄)^-={4}.

可见5+n个点的色集合彼此互异,故上述Ⅰ-全染色是点可区别的.

当m≥5,n≥5时,

第1步:先给连接u_i与v_j的边进行染色,令f(u_iv_j)=i+j,1≤i≤m,1≤j≤n-1; f(u_iv_n)=(n+i+2)_m+n,f(u_iv₀)=i+n,1≤i≤m.

第2步:再给圈和轮的边进行染色,令

f(v_jv_j+1)=(j-1)_m+n,j∈{1,2,…,n-1};

f(v_nv₁)=n+2; f(v₀v_j)=j,j∈{1,2,…,n}.

f(u_iu_i+1)=(i-1)_m+n,i∈{1,2,…,m-1};

f(u_mu₁)=1.

第3步:最后给点染色,令

f(u_i)=n+i,i≠m; f(u_m)=m+n-2.

f(v₀)=m+n,f(v_j)=j,j∈{1,2,…,n}.

上述染色是I-全染色,并且在此染色下有

C(u_i)={(i-2)_m+n,i-1,i+1,i+2,…,i+n,

(i+n+2)_m+n},i≠1,m;

C(u₁)={1,2,…,n+1,n+3,m+n},

C(u_m)={m-2,m+1,m+2,…,m+n,1,2},

C(v_j)={(j-2)_m+n,j-1,j,…,j+m},j≠1,n;

C(v₁)={1,2,…,m+1,n+2,m+n},

C(v_n)={n-2,n,n+2,n+3,…,m+n,1,2}.

C(v₀)^-=.

可见m+n+1个点的色集合彼此互异,故上述Ⅰ-全染色是点可区别的.

情形2:m>n

当m≥5,n=4时,令

f(u_iv_j)=i+j,j=1,2,3,4,i=1,2,…,m-1;

f(u_mv_j)=m+j+1,j≠4; f(u_mv₄)=2.

f(u_iv₀)=i,i≠1; f(u₁v₀)=m+2.

f(v_jv₀)=m+j,j≠2; f(v₂v₀)=1.

f(v₁v₂)=m+4,f(v₂v₃)=2,f(v₃v₄)=3,

f(v₄v₁)=1.

f(u_iu_i+1)=(i-1)_m+4,i≠m; f(u_mu₁)=1.

f(v_j)=f(v_jv₀),j≠4; f(v₄)=1.

f(v₀)=m+4,f(u_i)=f(u_iv₀).

上述染色是Ⅰ-全染色,并且在此染色下有

C(u_i)={(i-2)_m+4,i-1,i,i+1,i+2,i+3,

i+4},i{1,m};

C(u₁)={1,2,3,4,5,m+2,m+4};

C(u_m)={m-2,m,m+2,m+3,m+4,1,2}.

C(v₀)^-=,C(v₁)^-={m+3},

C(v₂)^-={m+2},C(v₃)^-={1},C(v₄)^-={4}.

可见m+5个点的色集合彼此互异,故上述Ⅰ-全染色是点可区别的.

当m≥6,n≥5时,

第1步:先给连接u_i与v_j的边进行染色,令 f(u_iv_j)=i+j,1≤i≤m-1,1≤j≤n; f(u_mv_j)=(m+j+2)_m+n,f(u_iv₀)=i,1≤i≤m.

第2步:再给圈和轮的边进行染色,令

f(v_jv_j+1)=(j-1)_m+n,j∈{1,2,…,n-1};

f(v_nv₁)=1; f(v₀v_j)=m+j,j∈{1,2,…,n}.

f(u_iu_i+1)=(i-1)_m+n,i∈{1,2,…,m-1};

f(u_mu₁)=m+2.

第3步:最后给点染色,令

f(u_i)=i,1≤i≤m; f(v_j)=m+j,j≠n;

f(v_n)=m+n-2,f(v₀)=m+n.

上述染色是Ⅰ-全染色,并且在此染色下有

C(u_i)={(i-2)_m+n,i-1,i,i+1,…,i+n},i≠1,m;

C(u₁)={1,2,…,n+1,m+2,m+n},

C(u_m)={m-2,m,m+2,m+3,…,m+n,1,2},

C(v_j)={(j-2)_m+n,j-1,j+1,j+2,…,j+m,(j+m+2)_m+n},j≠1,n;

C(v₁)={1,2,…,m+1,m+3,m+n},

C(v_n)={n-2,n+1,n+2,…,m+n,1,2}.

C(v₀)^-=.

可见m+n+1个点的色集合彼此互异,故上述Ⅰ-全染色是点可区别的.

因此,不管哪种情形所得到的染色f都是C_m∨W_n的一个VDIT染色.

定理3 设C_m∨F_n是圈和扇的联,且 n≥3,m≥3,则χⁱ_vt(C_m∨F_n)={m+4,n=3,m≥3;

n+4,m=3,n≥4;

m+n,m≥4,n≥4.

证明 Δ(C_m∨F_n)=Δ(C_m∨W_n),在第1种情况下C_m∨F_n有2个最大度顶点(而C_m∨W_n有4个最大度顶点),在第2种情况下C_m∨F_n有4个最大度顶点(此时C_m∨W_n有4个最大度顶点),在第3种情况下C_m∨F_n有1个最大度顶点(此时C_m∨W_n有1个最大度顶点),故本定理给出的具体数值作为χⁱ_vt(C_m∨F_n)的下界是合理的.下面只需给出各种情况下C_m∨F_n的合适的VDIT染色即可.事实上,在定理2的证明过程中的各种情形下所给出的带有VDIT染色的 C_m∨W_n的基础上删除边v_nv₁及其颜色便可得到C_m∨F_n的合适的VDIT染色.

定理4 设G∈{C_m∨C_n(n>m≥3),C_m∨W_n(m,n≥3),C_m∨F_n(m,n≥3)},则有χⁱ_vt(G)=χ^vi_vt(G)=ζ(G),即VDITC猜想和VDVITC猜想对以上3类图成立.

证明 由定理1及引理4可推出G=C_m∨C_n时定理成立.由定理2的前2种情况、引理4和定理2的第3种情况以及引理5可推出G=C_m∨W_n成立.由定理3的前2种情况,引理4和定理3的第3种情况及引理5可推出G=C_m∨F_n成立.