×Pn 的r-多彩著色?

張春梅，史雅馨，李越鋒

(新疆大學數(shù)學與系統(tǒng)科學學院，新疆烏魯木齊 830017)

0 引言

本文所研究的圖是簡單有限圖,E(G)和V(G)分別表示G的邊集和頂點集. 在圖G中,頂點vi的度數(shù)(記為d(vi))是與其關(guān)聯(lián)的邊數(shù), 其中δ(G)和?(G)表示圖G中的最小和最大頂點度.

記Pk+1為長度為k的路. 若P2是一個頂點集為V(P)={u0,u1,···,uk}(若i/=j,則ui/=uj),邊集為E(P)={u0u1,u0u2,u1u2,u1u3,···,uk-2uk,uk-1uk}的圖,則稱圖P2是路的平方圖. 下面我們設(shè)圖G={V(G),E(G)},H={V(H),E(H)}, 則頂點集為V(G)×V(H)={(u,v)|u∈V(G),v∈V(H)},邊集為E(G×H)={(ui,vj)(ux,vy)|(ui,vj)和(ux,vy)相鄰,當且僅當(ui,ux)∈E(G)且(vj,vy)∈E(H)},圖G和H的直積記作G×H.圖G的正常頂點著色是映射c:V(G)→L,該映射具有性質(zhì):如果u,v是相鄰的兩個點,則c(u)和c(v)是不同的.頂點k-著色是滿足|L|=k的正常頂點著色. 使G具有頂點k-著色的最小整數(shù)k稱為G的色數(shù), 用χ(G)表示. Chen 等[1]提出了如果對于每個度數(shù)至少為2 的頂點v,v的鄰點至少接收兩種不同的顏色,則一個正常的頂點k-著色稱為2-動態(tài)著色.使G具有2-動態(tài)著色的最小正整數(shù)k稱為圖G的2-動態(tài)色數(shù),并用χ2(G)表示.此外,2-動態(tài)著色通常也被稱為動態(tài)著色.通常,如果對于度數(shù)至少為r的每個頂點v的鄰點至少接收r種不同的顏色,則正常的頂點k-著色稱為(k,r)-著色.使G具有(k,r)-著色的最小正整數(shù)k稱為G的r-多彩色數(shù),并用χr(G)表示.

對于任意圖的r-多彩著色數(shù)χr(G),Lai 等[2]得到了以下規(guī)律:

并研究了χr(G),?(G)以及|V(G)|的關(guān)系:

關(guān)于一些直積圖的著色,Deepa 等[3]對圖Pm×Pn的r-多彩色數(shù)χr(Pm×Pn)進行了刻畫,得到了結(jié)果:

同時,Deepa 等對圖Pm×Cn的r-多彩色數(shù)χr(Pm×Cn)也進行了刻畫,下面給出部分結(jié)果:

關(guān)于著色的其它結(jié)果參閱文獻[4-7].基于此，本文研究了路的平方圖和路的直積圖的r-多彩色數(shù), 對于任意的正整數(shù)r,我們得到了r-多彩色數(shù)的精確值.

本文用矩陣

我們根據(jù)r的不同取值分別討論r=1,2,3,4,5,6,7,8 以及r>8 的情況.

定理1當整數(shù)n,m≥3,有χ1(×Pn)=2.

證明需要考慮兩種情形:

情形1當m=3 時,則?(×Pn)=4,由式(2),χr(G)≥min{r,?(G)}+1,有χ1(×Pn)≥2.由于d(u1,v1)=2,設(shè)c(u1,v1)=1, 則c(u2,v2)=c(u3,v2)=2,可得c(u1,v3)=c(u2,v1)=c(u2,v3)=c(u3,v1)=c(u3,v3)=1.同理可推導出圖×Pn滿足著色

此著色下,每個點(ui,vj)滿足|c(N(ui,vj))|= min{1,d(ui,vj)},因此χ1(×Pn)≤2,所以χ1(×Pn)=2.

情形2當m≥4 時,則?(×Pn)≥6,由式(2),χr(G)≥min{r,?(G)}+1,有χ1(×Pn)≥2,同情形1 類似,可推導出圖×Pn滿足著色

此著色下,每個點(ui,vj)滿足|c(N(ui,vj))|= min{1,d(ui,vj)},因此χ1(×Pn)≤2,所以χ1(×Pn)=2.

定理2當整數(shù)n,m≥3,有χ2(×Pn)=3.

證明需要考慮兩種情形:

情形1當m=3 時,則?(×Pn)=4,由式(2),χr(G)≥min{r,?(G)}+1,有χ2(×Pn)≥3.由于d(u1,v1)=2,設(shè)c(u1,v1)=1,則c(u2,v2)=2,c(u3,v2)=3,可得c(u1,v3)=1,c(u3,v1)=3,c(u3,v3)=3.因此我們可以得到c是圖×Pn的一個如下的3-著色

此著色下,每個點(ui,vj)滿足|c(N(ui,vj))|= min{2,d(ui,vj)},可推出c是圖×Pn的一個(3,2)-著色,所以χ2(×Pn)≤3,因此χ2(×Pn)=3.

情形2當m≥4 時,則?(×Pn)≥6,由式(2),χr(G)≥min{r,?(G)}+1,有χ2(×Pn)≥3.用情形1 的方法,我們可以得到c是圖×Pn的一個如下的3-著色

顯然, 此著色下, 每個點(ui,vj) 滿足|c(N(ui,vj))| = min{2,d(ui,vj)}, 所以c是圖×Pn的(3,2)-著色, 故χ2(×Pn)≤3,因此χ2(×Pn)=3.

定理3當整數(shù)n,m≥3,有

證明需要考慮三種情形:

情形1當m=3 時,則有?(×Pn)=4,由式(2),χr(G)≥min{r,?(G)}+1,有χ3(×Pn)≥4.因此我們可以得到c是圖×Pn的一個如下的4-著色

顯然,此著色下,每個點(ui,vj)滿足|c(N(ui,vj))|=min{3,d(ui,vj)},所以c是圖的(4,3)-著色,所以χ3(×Pn)≤4,因此χ3(×Pn)=4.

情形2當m= 4, 則有?(×Pn) = 6, 由式(2),χr(G) ≥min{r,?(G)}+1, 有χ3(×Pn) ≥4. 假設(shè)χ3(×Pn)=4,則×Pn有一個(4,3)-著色,因為d(u2,v1)=3 且N(u2,v1)={(u1,v2),(u3,v2),(u4,v2)},所以(u1,v2),(u3,v2),(u4,v2)著色互不相同,又因為d(u3,v1)=3 且N(u3,v1)={(u1,v2),(u2,v2),(u4,v2)},所以(u1,v2),(u2,v2), (u4,v2)著色兩兩不同,而d(u1,v1)=2,那么會有N(u1,v2)={(u2,v2),(u3,v2)},所以(u2,v2), (u3,v2)著色不同,綜上可知(u1,v2),(u2,v2),(u3,v2),(u4,v2)四個點著色互不相同,不妨設(shè)c(ui,v2)=i(1 ≤i≤4).因為相鄰頂點不能著相同的顏色, 所以c(u2,v1) /∈{1,3,4},c(u3,v1) /∈{1,2,4},c(u2,v3) /∈{1,3,4},c(u3,v3) /∈{1,2,4},從而c(u2,v1) = 2,c(u3,v1) = 3,c(u2,v3) = 2,c(u3,v3) = 3, 而N(u1,v2) = {(u2,v1),(u3,v1),(u2,v3),(u3,v3)}.|c(N(u1,v2))|=2 與|c(N(u1,v2))|≥3 矛盾,假設(shè)不成立,因此我們至少需要五種顏色進行著色,即χ3(×Pn)≥5,因此我們可以得到c是圖×Pn的一個如下5-著色顯然,此著色下,每個點(ui,vj)滿足|c(N(ui,vj))|≥min{3,d(ui,vj)},所以χ3(×Pn)≤5,因此χ3(×Pn)=5.

情形3m≥5時,則?(×Pn)=8,χ3(×Pn)≥4,與情形2 類似,我們至少需要五種顏色進行著色, 即χ3(×Pn)≥5.

(i)若m=0(mod 4),可以得到圖×Pn的5-著色形如

(ii)若m=1(mod 4),可以得到圖×Pn的5-著色形如

(iii)若m=2(mod 4),可以得到圖×Pn的5-著色形如

(iv)若m=3(mod 4),可以得到圖×Pn的5-著色形如

在上述著色下,每個點(ui,vj)滿足|c(N(ui,vj))|≥min{3,d(ui,vj)},所以χ3(×Pn)≤5,因此χ3(×Pn)=5.

定理4當整數(shù)n,m≥3,有χ4(×Pn)=6.

證明需要考慮三種情形:

情形1當m= 3 時, 則有?(×Pn) = 4, 由式(2),χr(G) ≥min{r,?(G)}+1, 有χ4(×Pn) ≥5. 因為d(u2,v2) = 4, 設(shè)c(u2,v2) = 1,c(u1,v1) = 2,c(u3,v1) = 3,c(u1,v3) = 4,c(u3,v3) = 5, 這個假設(shè)具有普適性且合理,因此我們可以得到c(u3,v2) ∈{3,5},如果c(u3,v2) = 3 或c(u3,v2) = 5,則c(u2,v1),c(u2,v3) /∈{2,3,4,5}且c(u2,v1)/=c(u2,v3).所以至少需要六種顏色進行著色,因此χ4(×Pn)≥6,我們令c(u3,v2)=3,c(u2,v1)=1,c(u1,v2)=2,則c(u2,v3)=6,c(u1,v4)/∈{2,3,5,6}.我們假設(shè)c(u1,v4)=4,則c(u3,v4)∈{1,5},c(u2,v4)∈{3,6},令c(u3,v4)=5,c(u2,v4)=6,則c(u1,v5),c(u3,v5)∈{1,2,3}且c(u1,v5)/=c(u3,v5),因此我們可以得到c是圖×Pn的一個如下的6-著色

顯然, 此著色下, 每個點(ui,vj) 滿足|c(N(ui,vj))| = min{4,d(ui,vj)}, 所以c是圖×Pn的(6,4)-著色, 所以χ4(×Pn)≤6,因此χ4(×Pn)=6.

情形2當m= 4 時, 則?(×Pn) = 6, 由式(2),χr(G) ≥min{r,?(G)}+1, 有χ4(×Pn) ≥5. 因為d(u1,v2)=4,設(shè)c(u1,v2)=1,c(u2,v1)=2,c(u3,v1)=3,c(u2,v3)=4,c(u3,v3)=5,這個假設(shè)具有普適性且合理,因此我們可以得到c(u4,v2) /∈{1,2,3,4,5},所以我們至少需要六種顏色進行著色,可以得到c是圖×Pn的一個如下的6-著色

顯然,此著色下,每個點(ui,vj)滿足|c(N(ui,vj))|=min{4,d(ui,vj)},故c是圖的(6,4)-著色,因此χ4(×Pn)=6.

情形3當m≥5 時,則?(×Pn)=8,與情形2 證明類似,可以得到c是圖×Pn的一個如下的6-著色

顯然,此著色下,每個點(ui,vj)滿足|c(N(ui,vj))|=min{4,d(ui,vj)},故c是圖的(6,4)-著色,因此χ4(×Pn)=6.

定理5當整數(shù)n,m≥3,有

證明需要考慮三種情形:

情形1當m=3 時,則有?(×Pn)=4,由式(2),χr(G)≥min{r,?(G)}+1,有χ5(×Pn)=χ4(×Pn)=6.

情形2當m= 4 時, 則有?(×Pn) = 6, 由式(2),χr(G) ≥min{r,?(G)}+1, 有χ5(×Pn) ≥6, 由于d(u2,v1)=3,設(shè)c(u2,v1)=1,c(u1,v2)=2,c(u3,v2)=3,c(u4,v2)=4,這個假設(shè)具有普適性且合理,因此我們可以得到c(u3,v1)=3,c(u2,v2)=1,c(u1,v1)∈{2,4},c(u4,v1)∈{2,4}.若c(u1,v1)=2 并且c(u4,v1)=2,那么我們可以得到c(u1,v3)=4,c(u3,v3)=5,c(u4,v3)=6,c(u2,v3) /∈{1,2,3,4,5,6},因此我們至少需要七種顏色進行著色.同理,若c(u1,v1)=4 且c(u4,v1)=4,我們同樣需要七種顏色.若c(u1,v1)=2 且c(u4,v1)=4,那么我們可以得到c(u2,v3)=5,c(u3,v3)=6,c(u1,v3) /∈{1,2,3,4,5,6},因此我們至少需要七種顏色進行著色,即χ5(×Pn)≥7,可以得到c是圖×Pn的一個如下的7-著色

顯然,此著色下,每個點(ui,vj)滿足|c(N(ui,vj))|=min{5,d(ui,vj)},所以c是圖的(7,5)-著色,所以χ5(×Pn)≤7.因此χ5(×Pn)=7.

情形3當m≥5,則有?(×Pn)=6,由式(2),χr(G)≥min{r,?(G)}+1,有χ5(×Pn)≥6,假設(shè)c(u2,v2)=1,c(u1,v1) = 2,c(u3,v2) = 3, 假設(shè)合理, 則c(u4,v1) = 2,c(u4,v2) = 2,c(u3,v1) = 3,c(u1,v2) = 4,c(u2,v1) = 1,c(u2,v3) = 5,c(u3,v3) = 6. 由于d(u2,v2) = 6, 所以c(u1,v3) /=c(u4,v3),c(u4,v3) ∈{4,5}. 假設(shè)c(u1,v3) = 4,c(u4,v3) = 5, 則c(u2,v4) = 2,c(u3,v4) = 6, 假設(shè)具有普適性, 由于d(u3,v3) = 8 且c(u5,v2) /= 5,c(u5,v4) /= 5,c(u1,v4)/=5,c(u4,v4)/=5,那么我們至少需要七種顏色進行著色.若c(u1,v3)=5,c(u4,v3)=4,則c(u2,v4)=2,c(u3,v4)=6,由于d(u3,v2)=8 且d(u4,v1)=4,那么c(u5,v2)=5,c(u5,v1)=6,所以c(u6,v3)/∈{1,2,3,4,5,6}.因此我們至少需要七種顏色進行著色,即χ5(×Pn)≥7,可以得到c是圖×Pn的一個如下的7-著色

顯然,此著色下,每個點(ui,vj)滿足|c(N(ui,vj))|= min{5,d(ui,vj)},c是圖的(7,5)-著色,所以χ5(×Pn)≤7.因此χ5(×Pn)=7.

定理6當整數(shù)n,m≥3,有

證明需要考慮三種情形:

情形1當m=3 時,則有?(×Pn)=4,由式(1)有χ6(×Pn)=χ4(×Pn)=6.

情形2當m=4 時,則有?(×Pn)=6,由式(1)有χ6(×Pn)≥7,由于d(u2,v2)=6,我們假設(shè)c(u2,v2)=1,c(u1,v1)=2,c(u3,v1)=3,c(u4,v1)=4,c(u1,v3)=5,c(u3,v3)=6,c(u4,v3)=7,則c(u2,v1)=1,則c(u2,v1)=1 且c(u2,v3)/∈{1,2,3,4,5,6,7},因此我們至少需要八種顏色進行著色,即χ6(×Pn)≥8,可以得到c是圖×Pn的一個如下的8-著色

顯然,此著色下,每個點(ui,vj)滿足|c(N(ui,vj))|=min{6,d(ui,vj)},則c是圖的(8,6)-著色,故χ6(×Pn)≤8.因此χ6(×Pn)=8.

情形3當m≥5 時,則有?(×Pn)=8,χ6(×Pn)≥7,我們假設(shè)c(u1,v1)=1,c(u2,v2)=2,c(u3,v2)=3,則c(u1,v2)=1,c(u2,v1)=2,c(u3,v1)=3,c(u4,v2)=4,c(u4,v1)=4,c(u5,v2)=5,則c(u2,v3)=5,c(u3,v3)=6.由于d(u2,v2)=6,所以c(u2,v4)∈{1,4},c(u3,v4)=6,c(u1,v4)/=c(u4,v4)且有c(u1,v4),c(u4,v4)∈{2,7}.由于d(u3,v3)=8,所以c(u5,v4)=3 或c(u5,v4)=5,無論c(u5,v4)=3 或c(u5,v4)=5,我們都能得到|c(N(u3,v3))|=5.因此,我們至少需要八種顏色進行著色,即χ6(×Pn)≥8,可以得到c是圖×Pn的一個如下的8-著色

顯然,此著色下,每個點(ui,vj)滿足|c(N(ui,vj))|=min{6,d(ui,vj)},則c是圖的(8,6)-著色,所以χ6(×Pn)≤8.因此χ6(×Pn)=8.

定理7當整數(shù)n,m≥3,有

證明需要考慮三種情形:

情形1當m=3 時,有?(×Pn)=4,由式(1)有χ7(×Pn)=χ4(×Pn)=6.

情形2當m=4 時,有?(×Pn)=6,由式(1)有χ7(×Pn)=χ6(×Pn)=8.

情形3當m≥5 時,有?(×Pn)=8,χ7(×Pn)≥8,由于d(u1,v2)=4,設(shè)c(u1,v2)=1,c(u2,v1)=2,c(u3,v1)=3,c(u2,v3)=4,c(u3,v3)=5,假設(shè)具有普適性且合理,因此我們可以得到c(u2,v2)∈{2,4}.若c(u2,v2)=2, 則c(u3,v3) ∈{3,5}. 若c(u3,v2) = 5, 則c(u4,v2) = 6,c(u5,v2) = 4,c(u4,v1) = 1,c(u6,v2) = 3,c(u4,v3) = 6.此時, |c(N(u3,v2))| = 4, 所以我們需要其它三種顏色來讓(u3,v2) 滿足7-動態(tài)色數(shù)的情況, 但是c(u1,v1) /= 3,c(u1,v3)/=3,c(u5,v1)/=3,c(u5,v3)/=3,因此我們需要7,8,9 三種顏色來滿足7-動態(tài)色數(shù)的情況.若c(u3,v2)=3,則c(u4,v2)=6,c(u5,v2)=4,c(u4,v1)=1,c(u6,v2)=5,c(u4,v3)=6.同理,|c(N(u3,v2))|=4,所以我們需要其它三種顏色來讓(u3,v2)滿足7-動態(tài)色數(shù)的情況,但是c(u1,v1)/=5,c(u1,v3)/=5,c(u5,v1)/=5,c(u5,v3)/=5,因此我們需要7,8,9 三種顏色來滿足7-動態(tài)色數(shù)的情況,同理,若c(u2,v2)=4,則c(u3,v2)∈{3,5},我們能夠得到結(jié)果,因此我們至少需要九種顏色進行著色,即χ7(×Pn)≥9,可以得到c是圖×Pn的一個如下的9-著色

顯然,此著色下,每個點(ui,vj)滿足|c(N(ui,vj))|=min{7,d(ui,vj)},則c是圖的(9,7)-著色,所以χ7(×Pn)≤9.因此χ7(×Pn)=9.

定理8當整數(shù)n,m≥3,有

證明需要考慮三種情形:

情形1當m=3 時,有?(×Pn)=4,由式(1)有χ8(×Pn)=χ4(×Pn)=6.

情形2當m=4 時,有?(×Pn)=6,由式(1)有χ8(×Pn)=χ6(×Pn)=8.

情形3當m≥5 時, 有?(×Pn) = 8,χ8(×Pn) ≥9, 由于d(u2,v1) = 3, 設(shè)c(u2,v1) = 1,c(u1,v2) =2,c(u3,v2) = 3,c(u4,v2) = 4, 這個假設(shè)具有普適性且合理, 因此我們可以得到c(u2,v2) = 1,c(u1,v1) ∈{2,4},c(u5,v2) = 5,c(u3,v1) = 3,c(u2,v3) = 5,c(u3,v3) = 6. 若設(shè)c(u1,v1) = 2, 則c(u4,v1) = 4,c(u1,v3) ∈{7,8},c(u4,v3)∈{7,8},c(u1,v3)/=c(u4,v3).若c(u1,v3)=7 且c(u4,v3)=8,則c(u3,v4)=6,c(u2,v4)=9,c(u1,v4)={7,8},無論c(u1,v4)=7 或c(u1,v4)=8,我們都能得到c(u5,v4)=10.同理,假設(shè)c(u1,v1)=4,則c(u4,v1)=2,我們使用相同的推斷方法可以得到一致的結(jié)論,即c(u5,v4)=10.因此我們至少需要十種顏色進行著色,即χ8(×Pn)≥10,可以得到c是圖×Pn的一個如下的10-著色

顯然,此著色下,每個點(ui,vj)滿足|c(N(ui,vj))|=min{8,d(ui,vj)},則c是圖的(10,8)-著色,所以χ8(×Pn)≤10.因此χ8(×Pn)=10.

定理9當整數(shù)n,m≥3,r>8 時,有

證明由圖×Pn的性質(zhì)知,?(×Pn)=8,且由式(1)得,χ8(×Pn)=χr(×Pn).

2 結(jié)論

我們解決了對于一般的正整數(shù)r,圖P2×P的多彩著色數(shù).在以后的工作中,我們可以研究包含圖P的圖類G與圖P2的圖類H(P∈G,P2∈H)的直積圖G×H的多彩著色數(shù).進一步,我們可以從圖G×G2的正常著色數(shù)入手,研究χ2(G×G2)和χ3(G×G2)的值以及對于一般的正整數(shù)r(r≥3),χr(G×G2)的值.