Kn□Km,s的r-hued染色

梁玲梅, 劉鳳霞, 賴虹建

(1.新疆大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院, 烏魯木齊 830046; 2.西弗吉尼亞大學(xué) 數(shù)學(xué)系, 美國 西弗吉尼亞 摩根城 26506)

1 引言與主要結(jié)果

(i) 對任意邊uv∈E(G), 有c(u)≠c(v);

(ii) 對任意頂點v∈V(G), 有|c(NG(v))|≥min{d(v),r}.

對于固定的整數(shù)r>0, 圖G的r-hued染色數(shù)[2-3]是指使圖G存在(k,r)-染色的最小正整數(shù)k, 記為χr(G).圖G的r-hued染色數(shù)相關(guān)性質(zhì)可參見文獻[4-9].

命題1[9]χr(Kn)=n.

命題2[9]設(shè)G是一個圖,r≥2, 則χr(G)≥min{Δ(G),r}+1.

設(shè)G和H是兩個圖, 圖G與圖H的笛卡爾積圖是指頂點集為V(G)×V(H)的圖, 記為G□H.任意兩個頂點(u,v)和(x,y)相鄰當(dāng)且僅當(dāng)u=x且vy∈E(H)或v=y且ux∈E(G).根據(jù)定義知,Δ(G□H)=Δ(G)+Δ(H).

關(guān)于兩個圖的笛卡爾積圖的r-hued染色數(shù)的研究目前已有很多結(jié)果.Suil[10]證明了對任意兩個圖G和H, 如果δ(G)≥r, 則χr(G□H)≤max{χr(G),χ(H)}; Akbari等[11]分別刻畫了路與路、路與圈、圈與圈的笛卡爾積圖的2-hued染色數(shù); Kang等[12]證明了如果mn≡2(mod 4), 則χ3(Pn□Pm)=5, 其中Pn表示n個頂點的路; Jahanbekam等[13]刻畫了路與路的笛卡爾積圖的3-hued染色數(shù)和4-hued染色數(shù); Shao等[14]刻畫了路與路的平方圖的笛卡爾積圖的r-hued染色數(shù); Kaliraj等[15]刻畫了完全圖與星圖的笛卡爾積圖的2-hued染色數(shù), 以及完全圖與輪圖的笛卡爾積圖的2-hued染色數(shù), 并給出了完全圖和完全二部圖的笛卡爾積圖的2-hued染色數(shù)為

本文將文獻[15]的結(jié)果推廣到更一般的正整數(shù)r上, 主要結(jié)果如下：

定理1設(shè)Kn□Km,s是一個笛卡爾積圖,m≥s≥2, 則

2 主要結(jié)果的證明

設(shè)完全圖Kn的頂點集為V(Kn)={v1,v2,…,vn}, 完全二部圖Km,s的頂點集為V(Km,s)={u1,u2,…,um,w1,w2,…,ws},m≥s≥2, 由笛卡爾積圖的定義, 本文按如下方式記Kn□Km,s的頂點集:

為方便, 記V(Kn□Km,s)=X∪Y, 這里X={viuj|1≤i≤n, 1≤j≤m},Y={viwk|1≤i≤n, 1≤k≤s}.從而可得

(1)

(2)

則有

d(viuj)=n-1+s,d(viwk)=n-1+m,

Δ(Kn□Km,s)=Δ(Kn)+Δ(Km,s)=n-1+m.

本文約定用n×(m+s)階矩陣的各元素表示V(Kn□Km,s)對應(yīng)頂點的染色.

定理2假設(shè)r

證明： 由于Kn□Km,s總包含Kn, 因此由命題1有χr(Kn□Km,s)≥χr(Kn)=n.

下面給出Kn□Km,s的一個具體(n,r)-染色, 以此說明χr(Kn□Km,s)≤n.定義映射c1:V(Kn□Km,s)→{1,2,3,…,n}為

即c1(V(Kn□Km,s))=A.由矩陣A知, 當(dāng)i≠t時,c1(viuj)≠c1(vtuj),c1(viwk)≠c1(vtwk),c1(viuj)≠c1(viwk), 且A中每個元素都滿足1≤aij≤n, 因此c1是Kn□Km,s的一個n-染色.下面證明映射c1滿足條件(ii).對于viuj∈X這類頂點, 由式(1)可得|NKn□Km,s(viuj)|=n-1+s, 而s≥2,n>r, 因此d(viuj)=n-1+s>r.當(dāng)1≤i≤n-1時,c1(NKn□Km,s(viuj))={1,2,…,n}{i+1}; 當(dāng)i=n時,c1(NKn□Km,s(viuj))={2,3,…,n}.從而

|c1(NKn□Km,s(uivj))|=n-1≥min{d(viuj),r}=min{n-1+s,r}=r.

對于viwk∈Y這類頂點, 由式(2)可得|NKn□Km,s(viwk)|=n-1+m, 則d(viwk)=n-1+m>r.又因為c1(NKn□Km,s(viwk))={1,2,…,n}{i}, 所以

|c1(NKn□Km,s(viwk))|=n-1≥min{d(viwk),r}=min{n-1+m,r}=r.

因此c1是Kn□Km,s的一個(n,r)-染色, 故χr(Kn□Km,s)≤n.綜上所述,χr(Kn□Km,s)=n.證畢.

下面總假設(shè)r≥n.根據(jù)r與圖Kn□Km,s的最大度和最小度的大小關(guān)系分類討論.當(dāng)r小于Kn□Km,s的最小度時, 有如下結(jié)論.

定理3假設(shè)r

情形1)r-n+1≤n.

對于頂點viu1∈X, 要滿足條件(ii), 則有

|c(NKn□Km,s(viu1))|≥min{d(viuj),r}=min{n-1+s,r}=r,

故viu1的鄰點集至少可染r種不同顏色, 由于viu1在Kn中, 所以滿足正常染色時該點鄰點在X中已有(n-1)種不同顏色, 因此在Y中的鄰點至少有(r-n+1)種顏色.用W1,W2,…,Wr-n+1,…,Ws表示Kn在Kn□Km,s中Y部分的第1,2,3,…,r-n+1,…,s個拷貝, 于是可任意調(diào)整順序, 不妨設(shè)前(r-n+1)個是用來滿足X中頂點條件(ii)的.對于X中第一列頂點, 由于在Kn中, 不妨設(shè)染色為c(viu1)=i(1≤i≤n), 因此要使點v1u1滿足條件(ii), 則W1中的頂點c(v1w1)?{1,2,3,…,n}, 不妨設(shè)c(v1w1)=n+1.要使點v2u1滿足條件(ii), 由v1w1與v2w1在W1中可知,W1中的頂點c(v2w1)?{1,2,3,…,n,n+1}, 不妨設(shè)c(v2w1)=n+2.同理c(v3w1)?{1,2,3,…,n,n+1,n+2}, 不妨設(shè)c(v3w1)=n+3.以此類推, 可設(shè)c(vnw1)=2n.故V(Kn□Km,s)至少需要2n種不同顏色, 即χr(Kn□Km,s)≥2n.

下面給出Kn□Km,s的一個(2n,r)-染色, 以此說明χr(Kn□Km,s)≤2n.定義映射c2:V(Kn□Km,s)→{1,2,3,…,2n}如下:

即c2(V(Kn□Km,s))=B=B1∪B2, 這里B1是X中頂點的染色方式,B2是Y中頂點的染色方式.由矩陣B可知, 當(dāng)i≠t時,c2(viuj)≠c2(vtuj),c2(viwk)≠c2(vtwk),c2(viuj)≠c2(viwk), 且B中每個元素都滿足1≤bij≤2n, 因此c2是Kn□Km,s的一個2n-染色.

下面證明映射c2滿足條件(ii).對于viuj∈X這類頂點, 由式(1), 有|NKn□Km,s(viuj)|=n-1+s, 則d(viuj)=n-1+s>r.由矩陣B可知, 頂點viuj的鄰點集在X中有(n-1)種不同顏色屬于{n+1,n+2,…,2n}, 在Y中有(r-n+1)種不同顏色屬于{1,2,…,n}, 從而

|c2(NKn□Km,s(uivj))|=n-1+(r-n+1)=r≥min{d(viuj),r}=min{n-1+s,r}=r.

對于viwk∈Y這類頂點, 由式(2)可得|NKn□Km,s(viwk)|=n-1+m, 則d(viwk)=n-1+m≥n-1+s>r.由矩陣B可知, 頂點viwk的鄰點集在Y中有(n-1)種不同顏色屬于{1,2,…,n}, 在X中有(r-n+1)種不同顏色屬于{n+1,n+2,…,2n}, 從而

|c2(NKn□Km,s(viwk))|=r≥min{d(viwk),r}=min{n-1+m,r}=r.

因此c2是Kn□Km,s的一個(2n,r)-染色, 即χr(Kn□Km,s)≤2n.綜上所述,χr(Kn□Km,s)=2n.

情形2)r-n+1>n.

對于頂點v1uj∈X, 要滿足條件(ii), 則

|c(NKn□Km,s(v1uj))|≥min{d(v1uj),r}=min{n-1+s,r}=r,

故v1uj的鄰點集至少可染r種不同顏色.由于v1uj在Kn中, 所以滿足正常染色時v1uj的X中鄰點已有(n-1)種不同顏色, 因此在Y中的鄰點, 即Y的第一行頂點至少需要(r-n+1)種顏色.對于頂點v1wk∈Y, 由條件(ii), 有

|c(NKn□Km,s(v1wk))|≥min{d(v1wk),r}=min{n-1+m,r}=r,

故v1wk的鄰點集至少可染r種不同顏色, 由于v1wk在Kn中, 所以滿足正常染色時v1wk的Y中鄰點已有(n-1)種不同顏色, 因此在X中的鄰點, 即X的第一行頂點至少需要(r-n+1)種顏色.又因為同一行頂點是完全二部圖的頂點, 故X和Y中第一行頂點染色必須不同, 于是V(Kn□Km,s)的第一行至少需要2(r-n+1)種不同顏色, 從而V(Kn□Km,s)至少需要2(r-n+1)種不同顏色, 即χr(Kn□Km,s)≥2(r-n+1).

下面給出Kn□Km,s的一個(2(r-n+1),r)-染色, 以此說明χr(Kn□Km,s)≤2(r-n+1).定義映射c3:V(Kn□Km,s)→{1,2,3,…,2(r-n+1)}如下:

即c3(V(Kn□Km,s))=C=C1∪C2, 這里:C1是X中頂點的染色方式, 該矩陣元素均小于等于2(r-n+1), 若有元素大于2(r-n+1), 則從r-n+2重新開始循環(huán);C2是Y中頂點的染色方式, 該矩陣元素均小于等于 (r-n+1), 若有元素大于(r-n+1), 則重新從1開始循環(huán).由矩陣C可知, 當(dāng)i≠t時,c3(viuj)≠c3(vtuj),c3(viwk)≠c3(vtwk),c3(viuj)≠c3(viwk), 且C中每個元素都滿足1≤cij≤2(r-n+1), 因此c3是Kn□Km,s的一個2(r-n+1)-染色.

下面證明映射c3滿足條件(ii).對于viuj∈X這類頂點, 由式(1)有|NKn□Km,s(viuj)|=n-1+s, 則d(viuj)=n-1+s≥r.由矩陣C可知, 頂點viuj的鄰點集在X中有(n-1)種不同顏色屬于{r-n+1+1,r-n+1+2,…,2(r-n+1)}, 在Y中有(r-n+1)種不同顏色屬于{1,2,…,r-n+1}, 從而

|c3(NKn□Km,s(uivj))|=r≥min{d(viuj),r}=min{n-1+s,r}=r.

對于viwk∈Y這類頂點, 由式(2)可得|NKn□Km,s(viwk)|=n-1+m, 則d(viwk)=n-1+m>r.由矩陣C可知, 頂點viwk的鄰點集在Y中有(n-1)種不同顏色屬于{1,2,…,r-n+1}, 在X中有(r-n+1)種不同顏色屬于{r-n+1+1,r-n+1+2,…,2(r-n+1)}, 于是

|c3(NKn□Km,s(viwk))|=r≥min{d(viwk),r}=min{n-1+m,r}=r.

因此c3是Kn□Km,s的一個(2(r-n+1),r)-染色, 即χr(Kn□Km,s)≤2(r-n+1).綜上所述,χr(Kn□K1,s)=2(r-n+1).證畢.

當(dāng)r介于Kn□Km,s的最小度和最大度之間時, 有如下結(jié)論.

定理4假設(shè)n-1+s≤r≤n-1+m, 則χr(Kn□Km,s)=max{2n,r+1,s+r-n+1}.

情形1)n≥s.

①n≥r-n+1.對于頂點viu1∈X, 要滿足條件(ii), 則

|c(NKn□Km,s(viu1))|≥min{d(viu1),r}=min{n-1+s,r}=n-1+s,

故viu1的鄰點集至少可染(n-1+s)種不同顏色, 由于viu1在Kn中, 所以滿足正常染色時該點鄰點在X中已有(n-1)種不同顏色, 因此在Y中的鄰點至少要貢獻s種顏色, 于是Y中第一行元素必須與X中第一列元素不同.由于X中第一列頂點在Kn中, 不妨設(shè)染色為c(viu1)=i(1≤i≤n).用W1,W2,…,Ws表示Kn在Kn□Km,s中Y部分的第1,2,3,…,s個拷貝, 因此W1中的頂點c(v1w1)?{1,2,3,…,n}, 不妨設(shè)c(v1w1)=n+1.要使v2u1滿足條件(ii), 由v1w1與v2w1在W1中可知,W1中的頂點c(v2w1)?{1,2,3,…,n,n+1}, 不妨設(shè)c(v2w1)=n+2.同理c(v3w1)?{1,2,3,…,n,n+1,n+2}, 不妨設(shè)c(v3w1)=n+3.以此類推, 可設(shè)c(vnw1)=2n.故V(Kn□Km,s)至少需要2n種不同顏色, 即χr(Kn□Km,s)≥2n.

下面給出Kn□Km,s的一個(2n,r)-染色, 以此說明χr(Kn□Km,s)≤2n.定義映射c4:V(Kn□Km,s)→{1,2,3,…,2n}如下:

即c4(V(Kn□Km,s))=D.由矩陣D知, 當(dāng)i≠t時,c4(viuj)≠c4(vtuj),c4(viwk)≠c4(vtwk),c4(viuj)≠c4(viwk), 且D中每個元素都滿足1≤dij≤2n, 因此c4是Kn□Km,s的一個2n-染色.下面證明映射c4滿足條件(ii).對于viuj∈X這類頂點, 由式(1)有|NKn□Km,s(viuj)|=n-1+s, 則d(viuj)=n-1+s≤r.由矩陣D可知, 頂點viuj的鄰點集在X中有(n-1)種不同顏色屬于{n+1,n+2,…,2n}, 在Y中有s種不同顏色屬于{1,2,…,n}, 從而

|c4(NKn□Km,s(uivj))|=n-1+s≥min{d(viuj),r}=min{n-1+s,r}=n-1+s.

對于viwk∈Y這類頂點, 由式(2)可得|NKn□Km,s(viwk)|=n-1+m, 則d(viuj)=n-1+m>r.又由矩陣D可知, 頂點viwk的鄰點集在Y中有(n-1)種不同顏色屬于{1,2,…,n}, 在X中有(r-n+1)種不同顏色屬于{n+1,n+2,…,2n}, 于是

|c(NKn□Km,s(viwk))|=r≥min{d(viwk),r}=min{n-1+m,r}=r.

因此c4是Kn□Km,s的一個(2n,r)-染色, 即χr(Kn□Km,s)≤2n.綜上所述,χr(Kn□Km,s)=2n.

②n

χr(Kn□Km,s)≥min{Δ(Kn□Km,s),r}+1=min{n-1+m,r}+1=r+1.

下面給出Kn□Km,s的一個(r+1,r)-染色, 以此說明χr(Kn□Km,s)≤r+1.定義映射c5:V(Kn□Km,s)→{1,2,3,…,r+1}如下:

即c(V(Kn□Km,s))=E.由矩陣E知, 當(dāng)i≠t時,c5(viuj)≠c5(vtuj),c5(viwk)≠c5(vtwk),c5(viuj)≠c5(viwk), 且E中每個元素都滿足1≤eij≤r+1, 因此c5是Kn□Km,s的一個(r+1)-染色.下面證明映射c5滿足條件(ii).對于viuj∈X這類頂點, 由式(1)有|NKn□Km,s(viuj)|=n-1+s, 則d(viuj)=n-1+s≤r.由矩陣E可知, 頂點viuj的鄰點集在X中有(n-1)種不同顏色屬于{n+1,n+2,…,n+r-n+1}, 在Y中有s種不同顏色屬于{1,2,…,n}, 從而

|c5(NKn□Km,s(uivj))|=n-1+s≥min{d(viuj),r}=min{n-1+s,r}=n-1+s.

對于viwk∈Y這類頂點, 由式(2)可得|NKn□Km,s(viwk)|=n-1+m, 則d(viwk)=n-1+m>r.又由矩陣D可知, 頂點viwk的鄰點集在Y中有(n-1)種不同顏色屬于{1,2,…,n}, 在X中有(r-n+1)種不同顏色屬于{n+1,n+2,…,n+r-n+1}, 從而

|c5(NKn□Km,s(viwk))|=r≥min{d(viwk),r}=min{n-1+m,r}=r.

因此c5是Kn□Km,s的一個(r+1,r)-染色, 即χr(Kn□Km,s)≤r+1.綜上所述,χr(Kn□Km,s)=r+1.

情形2)n

若n≥r-n+1, 則r-n+1

|c(NKn□Km,s(v1uj))|≥min{d(v1uj),r}=min{n-1+s,r}=n-1+s,

故v1uj的鄰點集至少可染(n-1+s)種不同顏色, 由于v1uj在Kn中, 所以滿足正常染色時在X中已有(n-1)不同顏色, 因此在Y中的第一行頂點至少需要s種顏色.對于頂點v1wk∈Y, 要滿足條件(ii), 則

|c(NKn□Km,s(v1wk))|≥min{d(v1wk),r}=min{n-1+m,r}=r,

故v1wk的鄰點集至少可染r種不同顏色, 由于v1wk在Kn中, 所以滿足正常染色時在Y中已有(n-1)種不同顏色, 因此在X中的第一行頂點至少需要(r-n+1)種顏色.又因為同一行頂點是完全二部圖的頂點, 故第一行X和Y中頂點染色必須不同, 于是V(Kn□Km,s)的第一行至少需要(s+(r-n+1))種不同顏色, 因此V(Kn□Km,s)至少需要(s+(r-n+1))種不同顏色, 即χr(Kn□Km,s)≥s+(r-n+1).

下面給出Kn□Km,s的一個(s+r-n+1,r)-染色, 以此說明χr(Kn□Km,s)≤s+r-n+1.定義映射c6:V(Kn□Km,s)→{1,2,3,…,s+r-n+1}如下:

即c6(V(Kn□Km,s))=F.由矩陣F知, 當(dāng)i≠t時,c6(viuj)≠c6(vtuj),c6(viwk)≠c6(vtwk),c6(viuj)≠c5(viwk), 且F知中每個元素都滿足1≤fij≤s+r-n+1, 因此c6是Kn□Km,s的一個(s+r-n+1)-染色.

下面證明映射c6滿足條件(ii).對于viuj∈X這類頂點, 由式(1)有|NKn□Km,s(viuj)|=n-1+s, 則d(viuj)=n-1+s≤r.由矩陣F可知, 頂點viuj的鄰點集在X中有(n-1)種不同顏色屬于{s+1,s+2,…,s+r-n+1}, 在Y中有s種不同顏色屬于{1,2,…,s}, 則

|c6(NKn□Km,s(uivj))|=n-1+s≥min{d(viuj),r}=min{n-1+s,r}=n-1+s.

對于viwk∈Y這類頂點, 由式(2)可得|NKn□Km,s(viwk)|=n-1+m, 則d(viwk)=n-1+m>r.又由矩陣F可知, 頂點viwk的鄰點集在Y中有(n-1)種不同顏色屬于{1,2,…,s}, 在X中有(r-n+1)種不同顏色屬于{s+1,s+2,…,s+r-n+1}, 從而

|c6(NKn□Km,s(viwk))|=r≥min{d(viwk),r}=min{n-1+m,r}=r.

因此c6是Kn□Km,s的一個(s+r-n+1,r)-染色, 即χr(Kn□Km,s)≤s+r-n+1.綜上所述,χr(Kn□Km,s)=s+r-n+1.證畢.

當(dāng)r大于Kn□Km,s的最大度時, 有如下結(jié)論.

定理5假設(shè)r>n-1+m, 則χr(Kn□Km,s)=max{2n,n+m,s+m}.

情形1)n≥s.

①n≥m.對于頂點viu1∈X, 要滿足條件(ii), 則

|c(NKn□Km,s(viu1))|≥min{d(viu1),r}=min{n-1+s,r}=n-1+s,

故viu1的鄰點集至少可染(n-1+s)種不同顏色, 由于viu1在Kn中, 所以滿足正常染色時該點鄰點在X中已有(n-1)種不同顏色, 因此在Y中的鄰點至少貢獻s種顏色.用W1,W2,…,Ws表示Kn在Kn□Km,s中Y部分的第1,2,3,…,s個拷貝, 則W1,W2,…,Ws中的頂點染色要滿足X中頂點的條件(ii), 對于X中第一列頂點, 由于在Kn中, 不妨設(shè)染色為c(viu1)=i(1≤i≤n), 因此要滿足v1u1的條件(ii), 則W1中的頂點c(v1w1)?{1,2,3,…,n}, 不妨設(shè)c(v1w1)=n+1.要滿足v2u1的條件(ii), 由v1w1與v2w1在W1中可知,W1中的頂點c(v2w1)?{1,2,3,…,n,n+1}, 不妨設(shè)c(v2w1)=n+2.同理c(v3w1)?{1,2,3,…,n,n+1,n+2}, 不妨設(shè)c(v3w1)=n+3.以此類推, 可設(shè)c(vnw1)=2n.因此V(Kn□Km,s)至少需要2n種不同顏色, 即χr(Kn□Km,s)≥2n.

下面給出Kn□Km,s的一個(2n,r)-染色, 以此說明χr(Kn□Km,s)≤2n.定義映射c7:V(Kn□Km,s)→{1,2,3,…,2n}如下:

即c7(V(Kn□Km,s))=G.由矩陣G知, 當(dāng)i≠t時,c7(viuj)≠c7(vtuj),c7(viwk)≠c7(vtwk),c7(viuj)≠c7(viwk), 且G中每個元素都滿足1≤gij≤2n, 因此c7是Kn□Km,s的一個2n-染色.

下面證明映射c7滿足條件(ii).對于viuj∈X這類頂點, 由式(1)有|NKn□Km,s(viuj)|=n-1+s, 則d(viuj)=n-1+s

|c7(NKn□Km,s(viuj))|=n-1+s≥min{d(viuj),r}=min{n-1+s,r}=n-1+s.

對于viwk∈Y這類頂點, 由式(2)可得|NKn□Km,s(viwk)|=n-1+m, 則d(viwk)=n-1+m≤r.又由矩陣G可知, 頂點viwk的鄰點集在Y中有(n-1)種不同顏色屬于{1,2,…,n}, 在X中有m種不同顏色屬于{n+1,n+2,…,2n}, 從而

|c7(NKn□Km,s(viwk))|=n-1+m≥min{d(viwk),r}=min{n-1+m,r}=n-1+m.

因此c7是Kn□Km,s的一個(2n,r)-染色, 即χr(Kn□Km,s)≤2n.綜上所述,χr(Kn□Km,s)=2n.

②n

χr(Kn□Km,s)≥min{Δ(Kn□Km,s),r}+1=min{n-1+m,r}+1=n+m.

下面給出Kn□Km,s的一個(n+m,r)-染色, 以此說明χr(Kn□Km,s)≤n+m.定義映射c8:V(Kn□Km,s)→{1,2,3,…,n+m}如下:

即c8(V(Kn□Km,s))=H.由矩陣H知, 當(dāng)i≠t時,c8(viuj)≠c8(vtuj),c8(viwk)≠c8(vtwk),c8(viuj)≠c8(viwk), 且H中每個元素都滿足1≤hij≤n+m.因此c8是Kn□Km,s的一個(n+m)-染色.

下面證明映射c8滿足條件(ii).對于viuj∈X這類頂點, 由式(1)可知, |NKn□Km,s(viuj)|=n-1+s, 則d(viuj)=n-1+s

|c8(NKn□Km,s(viuj))|=n-1+s≥min{d(viuj),r}=min{n-1+s,r}=n-1+s.

對于viwk∈Y這類頂點, 由式(2)可得|NKn□Km,s(viwk)|=n-1+m, 則d(viwk)=n-1+m≤r.又由矩陣G可知, 頂點viwk的鄰點集在Y中有(n-1)種不同顏色屬于{1,2,…,n}, 在X中有m種不同顏色屬于{n+1,n+2,…,n+m}, 從而

|c8(NKn□Km,s(viwk))|=n+m-1≥min{d(viwk),r}=min{n-1+m,r}=n-1+m.

因此c8是Kn□Km,s的一個(n+m,r)-染色, 即χr(Kn□Km,s)≤n+m.綜上所述,χr(Kn□Km,s)=n+m.

情形2)n

已知s≤m, 因此n

|c(NKn□Km,s(v1uj))|≥min{d(v1uj),r}=min{n-1+s,r}=n-1+s,

故v1uj的鄰點集至少可染(n-1+s)種不同顏色, 由于v1uj在Kn中, 所以滿足正常染色時鄰點集在X中已有(n-1)種不同顏色, 因此在Y中的第一行頂點至少需要s種顏色.對于頂點v1wk∈Y, 要滿足條件(ii), 則

|c(NKn□Km,s(v1wk))|≥min{d(v1wk),r}=min{n-1+m,r}=n-1+m,

故v1wk的鄰點集至少可染(n-1+m)種不同顏色, 由于v1wk在Kn中, 所以滿足正常染色時鄰點集在Y中已有(n-1)種不同顏色, 因此第一行在X中的頂點至少需要m種顏色.又因為同一行頂點是完全二部圖的頂點, 故第一行X和Y中頂點染色必須不同, 于是V(Kn□Km,s)的第一行至少需要(s+m)種不同顏色, 因此V(Kn□Km,s)至少需要(s+m)種不同顏色, 即χr(Kn□Km,s)≥s+m.

下面給出Kn□Km,s的一個(s+m,r)-染色, 以此說明χr(Kn□Km,s)≤s+m.定義映射c9:V(Kn□Km,s)→{1,2,3,…,s+m}如下:

即c9(V(Kn□Km,s))=P.由矩陣P知, 當(dāng)i≠t時,c9(viuj)≠c9(vtuj),c9(viwk)≠c9(vtwk),c9(viuj)≠c9(viwk), 且P中每個元素都滿足1≤pij≤s+m, 因此c9是Kn□Km,s的一個(s+m)-染色.

下面證明c9滿足條件(ii).對于viuj∈X這類頂點, 由式(1)有|NKn□Km,s(viuj)|=n-1+s, 則d(viuj)=n-1+s

|c9(NKn□Km,s(uivj))|=n+s-1≥min{d(viuj),r}=min{n-1+s,r}=n+s-1.

對于viwk∈Y這類頂點, 由式(2)可得|NKn□Km,s(viwk)|=n-1+m, 則d(viwk)=n-1+m

|c9(NKn□Km,s(viwk))|=n+m-1≥min{d(viwk),r}=min{n-1+m,r}=n+m-1.

因此c9是Kn□Km,s的一個(s+m,r)-染色, 即χr(Kn□Km,s)≤s+m.綜上所述,χr(Kn□Km,s)=s+m.

由定理2～定理5即可證得定理1.