摘要： 利用反證法、 色集合事先分配法和構(gòu)造染色法， 討論等完全p-部圖的頂點被多重集可區(qū)別的一般全染色， 給出最優(yōu)染色方案， 并確定相應(yīng)染色的色數(shù).

關(guān)鍵詞： 等完全p-部圖; 一般全染色; 多重集; 色集合; 可區(qū)別

中圖分類號： O157.5" 文獻標(biāo)志碼： A" 文章編號： 1671-5489（2024）03-0503-12

General Total Colorings of Complete p-Partite GraphsWhich Are Vertex-Distinguished by Multiple Sets

WANG Xuan， CHEN Xiang’en

（College of Mathematics and Statistics， Northwest Normal University， Lanzhou 730070， China）

Abstract： By using the method of proof by contradiction， the method of pre-assignment of color sets and the method of constructing coloring

， we discussed the general total coloring of" complete p-partite graphs which were vertex-distinguished by multiple sets， gave the coloring scheme

for optimal coloring and determined the chormatic numbers of the corresponding colorings.

Keywords： general p-partite graph; general total coloring; multiple set; color set; distinguishing

收稿日期： 2023-09-25.

第一作者簡介： 王" 萱（1999—）， 女， 漢族， 碩士研究生， 從事圖論及其應(yīng)用的研究， E-mail： wangxuan20220901@163.com. 通信作者簡介：

陳祥恩（1965—）， 男， 漢族， 碩士， 教授， 從事圖論及其應(yīng)用的研究， E-mail： chenxe@nwnu.edu.cn.

基金項目： 國家自然科學(xué)基金（批準(zhǔn)號： 11761064）.

目前， 關(guān)于圖的一般全染色問題研究已有很多成果. 例如： Harary等［1］提出了圖的點可區(qū)別一般邊染色問題; 文獻［2］引入了圖的點可區(qū)別

一般全染色， 并研究了路、 圈、 星（即K1，n）、 雙星、 三星、 輪、 扇和完全圖的一般點可區(qū)別全染色， 確定了它們的一般點可區(qū)別全色數(shù)； 文獻［3］研究了部分完全三部圖

的點（被非多重集）可區(qū)別的IE-全染色； 文獻［4］提出了點被多重集可區(qū)別的IE-全染色及一般全染色， 并研究了完全二部圖的點被多重集可區(qū)別的IE-全染色及一般全染色，

其中包括等完全二部圖的染色； 文獻［5］研究了完全四部圖Kn1，n2，n3，n4（n1≤n2=n3lt;n4或n1=n2=n3=n4）的點被多重集可區(qū)別的一般全染色， 給出了染色方案并確定相應(yīng)的點被多

重集可區(qū)別的一般全色數(shù)， 其中包括等完全四部圖的染色方案及點被多重集可區(qū)別的一般全色數(shù)； 文獻［6］研究了完全三部圖的點被多重集可區(qū)別的一般全染色；

文獻［7］綜述了關(guān)于某些頂點對被非多重色集合所區(qū)別的未必正常染色問題. 本文考慮等完全多部圖的點被多重集可區(qū)別的一般全染色， 給出染色方案并確定等完全多部圖的點被

多重集可區(qū)別的一般全色數(shù).

1" 預(yù)備知識

圖G的一般全染色是指用若干種元素對圖G的全體頂點及邊的一個分配， 通常進行染色時， 所用的k種顏色用1，2，…，k表示， 且數(shù)字代表的顏色之間有大小關(guān)系. 圖G使用k

種顏色的一般全染色稱為圖G的k-一般全染色. 設(shè)f為圖G的一般全染色， 對任意的x∈V（G）， 用f（x）或（x）表示點x的色以及與x關(guān)聯(lián)的邊的顏色構(gòu)成的多重集.

f（x）稱為x的多重色集合或色集合. 顯然f（x）=dG（x）+1， 其中dG（x）表示圖G中點x的度. 若對任意的u，v∈V（G）， u≠v， 總有f（u）≠f（v）

， 則稱f是點被多重集可區(qū)別的.

令χgvt（G）=min{kG存在點被多重集可區(qū)別的k-一般全染色}， χgvt（G）稱為點被多重集可區(qū)別的一般全色數(shù).

用K（p×q）表示每個部中頂點數(shù)目均為q的等完全p-部圖， 第i個部的第j個頂點為x（i）j， 第i個部為Xi={x（i）1，x（i）2，…，x（i）q}，

Xi=q， 1≤i≤p， 1≤j≤q.

設(shè)X，Y是圖G頂點集的兩個非空子集， 用（X，Y）表示一個頂點在X中， 另一個頂點在Y中的所有邊構(gòu)成的集合.

引理1［8］" 從n個互不相同元素中取出r個構(gòu)成的重復(fù)組合數(shù)為n+r-1r個.

從n個互不相同元素中取出r個構(gòu)成的重復(fù)組合稱為r-組合. r-組合也是上述n個互不相同元素構(gòu)成的集合含有r個元素的多重子集合， 所以 r-組合也稱為r-多重子集或簡稱

r-子集. 本文若無特殊說明， r-子集中的顏色按不減順序排列.

2" 主要結(jié)果

定理1" 當(dāng)p≥2， q=1時， χgvt（G）=2.

證明： 當(dāng)p≥2， q=1時， 圖G為p階完全圖Kp， 構(gòu)造一個p階對稱矩陣Mp， 使得次對角線及其上方的元素均為1， 而次對角線下方的元素均為2.

將Mp的（i，i）-元素（顏色）染給頂點x（i）1， i=1，2，…，p； 將Mp的（i，j）-元素染給邊x（i）1x（j）1， i≠j， 且i，j∈{1，2，…，p}.

圖1" K6使用兩種顏色的點可區(qū)別一般全染色Fig.1" Vertex-distinguishing general totalcolorings with two colors of K6

下面說明在上述染色方案下的一般全染色是點被多重集可區(qū)別的. 因為Mp的第i行元素構(gòu)成的多重集恰好是x（i）1的色集合， 且當(dāng)ilt;j時， （x（i）1）含1的數(shù)目比（x（j）1）含1的數(shù)目多， 故（x（i）1）≠（x（j）1）， 即點被多重集可區(qū)別.

例如， K6使用2種顏色的點被多重集可區(qū)別的一般全染色如圖1所示（其中顏色為1的邊未畫出， 顏色為2的邊已畫出）， 對應(yīng)的染色方案如下：

圖G為6階完全圖K6， 構(gòu)造一個6階對稱矩陣M6， 使得次對角線及其上方的元素均為1， 而次對角線下方的元素均為2，

M6=111111111112111122

111222112222122222.

將M6的（i，i）-元素（顏色）染頂點x（i）1， i=1，2，…，6； 將M6的（i，j）-元素染邊x（i）1x（j）1， i≠j， 且i，j∈

{1，2，…，6}. 于是， 所有的點及邊已染色. 下面列舉Xj（j=1，2，…，6）中點的色集合：

X1： （x（1）1）={1，1，1，1，1，1}，X2： （x（2）1）={1，1，1，1，1，2}，

X3： （x（3）1）={1，1，1，1，2，2}，X4： （x（4）1）={1，1，1，2，2，2}，

X5： （x（5）1）={1，1，2，2，2，2}，X6： （x（6）1）={1，2，2，2，2，2}，

χgvt（K6）=2.

定理2" 當(dāng)p≥2， q=2時， χgvt（G）=2.

證明： 當(dāng)q=2時， 圖G共有2p個頂點， 每個頂點的色集合對應(yīng)一個（2p-1）-子集（為方便， 證明過程中（2p-1）-子集的顏色未按不減

順序排列）. 將{1，2}兩種色的（2p-1）-子集（多重集）分為兩類.

第一類： 設(shè){1，2}兩種色的所有（2p-1）-子集多重集中1的數(shù)目比2的數(shù)目多的多重集為Ai， Ai中所含元素2的個數(shù)等于i. 第一項從A0起， 最后一項

到Ap-1止， 多重集Ai所含2的數(shù)目嚴(yán)格遞增， Ai中元素按從大到小的順序排列， 1≤i≤p-1. 例如， 當(dāng)p=6時，

A0={1，1，1，1，1，1，1，1，1，1，1}，" A1={2，1，1，1，1，1，1，1，1，1，1}，A2={2，2，1，1，1，1，1，1，1，1，1}，" A3={2，2，2，1，1，1，1，1，1，1，1}，

A4={2，2，2，2，1，1，1，1，1，1，1}，" A5={2，2，2，2，2，1，1，1，1，1，1}.

第二類： 將Ai對應(yīng)的（2p-1）-子集（多重集）中的元素1，2對調(diào)， 所得新的多重集記為du（Ai）， du（Ai）中含元素1的個數(shù)等于i（i=0，1，…，p-1）. 多重集du（

A0），du（A1），…，du（Ap-1）中所含元素1的數(shù)目嚴(yán)格遞增， du（Ai）中元素按從小到大的順序排列， 0≤i≤p-1. 例如， 當(dāng)p=6時，

du（A0）={2，2，2，2，2，2，2，2，2，2，2}，" du（A1）={1，2，2，2，2，2，2，2，2，2，2}，

du（A2）={1，1，2，2，2，2，2，2，2，2，2}，" du（A3）={1，1，1，2，2，2，2，2，2，2，2}，

du（A4）={1，1，1，1，2，2，2，2，2，2，2}，" du（A5）={1，1，1，1，1，2，2，2，2，2，2}.

將A0，A1，A2，…，Ap-1依次分別對應(yīng)到x（1）1，x（2）1，x（3）1，…，x（p）1， 將du（A0），du（A1），du（A2），…，

du（Ap-1）依次分別對應(yīng)到x（2）1，x（2）2，x（3）2，…，x（p）2. 于是x（i）1和x（i）2對應(yīng)的子集是互為對偶的， 1≤i≤p.

下面對K（p×2）的點、 邊進行染色， 使得x（i）1接受顏色1， x（i）2接受顏色2， 1≤i≤p. 將x（1）1的關(guān)聯(lián)邊都染顏色1， x（1）2的關(guān)聯(lián)邊都染顏色2. 將x（2）1未被染色的關(guān)聯(lián)邊都染

顏色1， x（2）2未被染色的關(guān)聯(lián)邊都染顏色2. 將x（3）1未被染色的關(guān)聯(lián)邊都染顏色1， x（3）2未被染色的關(guān)聯(lián)邊都染顏色2. 依次類推， 直到最后將

x（p-1）1未被染色的關(guān)聯(lián)邊都染顏色1， 將x（p-1）2未被染色的關(guān)聯(lián)邊都染顏色2. 最終得到K（p×2）的2-一般全染色. 該2-一般全染色是點被多

重集可區(qū)別的. 因為每個頂點的色集合剛好是染色前對應(yīng)該頂點的集合， 從而保證了不同點的色集合不同.

例如， K（6×2）的點被多重集可區(qū)別的2-一般全染色如圖2所示（其中顏色為1的邊未畫出， 顏色為2的邊已畫出）. 圖2中位置靠近的兩個頂點屬于同一部， 并給出了每個頂點的色集合.

圖2" K（6×2）的點被多重集可區(qū)別的2-一般全染色

Fig.2" 2＼|General total colorings" of K（6×2） which are vertex＼|distinguished by multiple sets

下面列舉Xj（j=1，2，…，6）中點的色集合：

X1： （x（1）1）={1，1，1，1，1，1，1，1，1，1，1}，" （x（1）2）={2，2，2，2，2，2，2，2，2，2，2}，

X2： （x（2）1）={2，1，1，1，1，1，1，1，1，1，1}，" （x（2）2）={1，2，2，2，2，2，2，2，2，2，2}，

X3： （x（3）1）={2，2，1，1，1，1，1，1，1，1，1}，" （x（3）2）={1，1，2，2，2，2，2，2，2，2，2}，

X4： （x（4）1）={2，2，2，1，1，1，1，1，1，1，1}，" （x（4）2）={1，1，1，2，2，2，2，2，2，2，2}，

X5： （x（5）1）={2，2，2，2，1，1，1，1，1，1，1}，" （x（5）2）={1，1，1，1，2，2，2，2，2，2，2}，

X6： （x（6）1）={2，2，2，2，2，1，1，1，1，1，1}，" （x（6）2）={1，1，1，1，1，2，2，2，2，2，2}.

定理3" 當(dāng)p≥2， q=3時， χgvt（G）=3.

證明： 當(dāng)q=3時， 圖G共有3p個頂點， 每個頂點的色集合對應(yīng)一個（3p-2）-子集. 首先證明圖G不存在使用2種色的點被多重集可區(qū)別的一般全染色. 用反證法.

假設(shè)圖G存在使用2種色的點被多重集可區(qū)別的一般全染色， 則由引理1可知， 2種色的（3p-2）

-子集共有（3p-1）個. 若要使2種色可染， 則需滿足（3p-2）-子集數(shù)大于圖G所含頂點數(shù). 顯然（3p-1）lt;3p， 矛盾. 下面構(gòu)造使用3種色的點被多重集可區(qū)別的一般全染色.

將{1，2，3}3種色的（3p-2）-子集（多重集）分為3類.

第一類： 在對應(yīng)部的3個頂點對應(yīng)的3個多重集中， 1的數(shù)目比2，3的數(shù)目多， 第一項從（x（1）1）起， 最后一項到（x（p）1）止， 多重集中1

的數(shù)目隨上標(biāo)的增大逐次遞減. 例如， 當(dāng)p=3時，

（x（1）1）={1，1，1，1，1，1，1}，（x（2）1）={1，1，1，1，1，2，3}，（x（3）1）={1，1，1，2，2，3，3}

均是對應(yīng)部所有多重集中含1數(shù)目最多的色集.

第二類： 在對應(yīng)部的3個頂點對應(yīng)的3個多重集中， 2的數(shù)目比1，3的數(shù)目多， 第一項從（x（1）2）起， 最后一項到（x（p）2）止， 多重集中2

的數(shù)目隨上標(biāo)的增大逐次遞減. 例如， 當(dāng)p=3時，

（x（1）2）={2，2，2，2，2，2，2}，（x（2）2）={1，2，2，2，2，2，3}，（x（3）2）={1，1，2，2，2，3，3}

均是對應(yīng)部所有多重集中含2數(shù)目最多的色集合.

第三類： 在對應(yīng)部的3個頂點對應(yīng)的3個多重集中， 3的數(shù)目比1，2的數(shù)目多， 第一項從（x（1）3）起， 最后一項到（x（p）3）止， 多重集中3

的數(shù)目隨上標(biāo)的增大逐次遞減. 例如， 當(dāng)p=3時，

（x（1）3）={3，3，3，3，3，3，3}，（x（2）3）={1，2，3，3，3，3，3}，（x（3）3）={1，1，2，2，3，3，3}

均是對應(yīng)部所有多重集中含3數(shù)目最多的色集合.

將（x（1）1），（x（2）1），…，（x（p）1）對應(yīng)到頂點x（1）1，x（2）1，…，x（p）1， 將（x（1）2）

，（x（2）2），…，（x（p）2）對應(yīng)到頂點x（1）2，x（2）2，…，x（p）2， 將（x（1）3），（x（2）3），…，（x（p）3）對應(yīng)到頂點x（1）3，x（2）3，…，x（p）3. 即將頂點與色集合一一對應(yīng).

下面對K（p×3）的點、 邊進行染色. 將x（i）1染顏色1， x（i）2染顏色2， x（i）3染顏色3. 令x（1）1的所有關(guān)聯(lián)邊均染顏色1， x（1）2的所有關(guān)聯(lián)邊均染顏色2， x（1

）3的所有關(guān)聯(lián)邊均染顏色3. 令x（2）1未被染色的關(guān)聯(lián)邊均染顏色1， x（2）2未被染色的關(guān)聯(lián)邊均染顏色2， x（2）3未被染色的關(guān)聯(lián)邊均染顏色3. 依次類推，

直到最后令x（p-1）1未被染色的關(guān)聯(lián)邊均染顏色1， x（p-1）2未被染色的關(guān)聯(lián)邊均染顏色2， x（p-1）3未被染色的關(guān)聯(lián)邊均染顏色3. 最后所有的頂點和邊

均已完成染色， 得到K（p×3）的3-一般全染色. 因為每個頂點的色集合剛好是染色前對應(yīng)該頂點的集合， 從而保證了不同點的色集合不同. 下面說明在這種染色方案下頂點的色集合各不相同.

1） 同一部中點的色集合各不相同.

由于（x（i）1）中含1的數(shù)目比（x（i）2），（x（i）3）中含1的數(shù)目多， （x（i）2）中含2的數(shù)目比（x（i）1），（x

（i）3）中含2的數(shù)目多， （x（i）3）中含3的數(shù)目比（x（i）1），（x（i）2）中含3的數(shù)目多， i=1，2，…，p， 故同一部中頂點的色集合各不相同.

2） 若兩個頂點屬于不同部， 則這兩個點的色集合不同.

當(dāng)1≤ilt;j-1≤p時， X1∪…∪Xi-1∪Xj+1∪…∪Xp中點與x（i）1所連色為1的邊的條數(shù)等于X1∪…∪Xi-1∪Xj+1∪…

∪Xp中點與x（j）1所連色為1的邊的條數(shù). x（i）1與Xi+1∪…∪Xj-1中點所連邊的色均為1， 而x（j）1與Xi+1∪…∪Xj-1中點所

連邊中僅有邊的13的色為1， 其余23的邊的色為2或3. 所以x（i）1與Xi+1

∪…∪Xj-1中點所連色為1的邊的條數(shù)比x（j）1與Xi+1∪…∪Xj-1中點所連色為1的邊的條數(shù)多， x（i）1與Xj中各點連邊的色均為1（共3條），

x（j）1與Xi中點所連邊只有1條色為1. 即（x（i）1）含1的數(shù)目比（x（j）1）含1的數(shù)目多. 同理可得（x（i）2）含2的數(shù)目比（x（j）2

）含2的數(shù)目多， （x（i）3）含3的數(shù)目比（x（j）3）含3的數(shù)目多.

對1≤ilt;j≤p， （x（i）1）含1的數(shù)目多于（x（j）1）含1的數(shù)目， 即x（i）1與x（j）1可區(qū)別， 而（x（j）1）含1

的數(shù)目比（x（j）2），（x（j）3）含1的數(shù)目多， 故（x（i）1）含1的數(shù)目比（x（j）2），（x（j）3）含1的數(shù)

目多. 從而x（i）2與x（j）1，x（j）3可區(qū)別. （x（i）3）含3的數(shù)目多于（x（j）3）含3的數(shù)目， 即x（i）3與x（j）3可區(qū)別，

圖3" K（3×3）的點被多重集可區(qū)別的3-一般全染色

Fig.3" 3＼|General total colorings of K（3×3） which arevertex＼|distinguished by multiple sets

而（x（j）3）含

3的數(shù)目比（x（j）1），（x（j）2）含3的數(shù)目多， 故（x（i）3）含3的數(shù)目比（（x（j）1），（x（j）2）含3的數(shù)目多. 從而x（i）

3與x（j）1，x（j）2可區(qū)別. 即若兩個頂點屬于不同部， 則這兩個點的色集合不同.

例如， K（3×3）的點被多重集可區(qū)別的3-一般全染色如圖3所示（其中顏色為3的邊未畫出， 顏色為1，2的邊已畫出）. 圖3中位置靠近的3個頂點屬于同一部， 并給出了每個頂點的色集合.

下面列舉Xj（j=1，2，3）中點的色集合：

X1： （x（1）1）={1，1，1，1，1，1，1}，" （x（1）2）={2，2，2，2，2，2，2}，" （x（1）3）={3，3，3，3，3，3，3}，

X2： （x（2）1）={1，1，1，1，1，2，3}，" （x（2）2）={1，2，2，2，2，2，3}，" （x（2）3）={1，2，3，3，3，3，3}，

X3： （x（3）1）={1，1，1，2，2，3，3}，" （x（3）2）={1，1，2，2，2，3，3}，" （x（3）3）={1，1，2，2，3，3，3}.

定理4" 當(dāng)p≥5， q≥4時， χgvt（G）=3.

證明： 對于等完全p-部圖K（p×q）， 其第i個部全體頂點構(gòu)成的集合為Xi， i=1，2，…，p. 設(shè)Iq為q階單位矩陣； Uq（i，j）表

示次對角線上方元素均為i， 而次對角線及其下方的元素均為j的q×q階矩陣； Lq（i，j）表示次對角線及其上方元素均為i， 而次對角線下方的元素均為j的q×q階矩陣，

1≤ilt;j≤3； Rq（i）表示元素均為i的q階方陣， 1≤i≤3; N表示元素均為3的q×1階矩陣.

一個元素或者是0或者是顏色的對稱矩陣A（n×n）稱為G的一個全染色（方案）矩陣， V（G）={v1，v2，…，vn}， A的（i，j）-元素（i≠j）是連接第i個頂點和第j個頂點的邊的顏色，

當(dāng)vi與vj（i≠j）間無邊時， A的（i，j）-元素為0， 當(dāng)vi與vj間有邊（i≠j）時， （i，j）-元素為邊的顏色， 且（i，i）-元素為頂點的顏色.

下面分別證明當(dāng)p=5， p=6， p≥7時， χgvt（G）=3.

1） 當(dāng)p=5， q≥4時， 圖G共有5q個頂點， 每個頂點的色集合對應(yīng)一個（4q+1）-子集.

先證明圖G不存在使用2種色的點被多重集可區(qū)別的一般全染色. 用反證法， 假設(shè)圖G存在使

用2種色的點被多重集可區(qū)別的一般全染色， 則由引理1可知， 2種色的（4q+1）-子集共有（4q+2）個. 若使2種色可染， 則需滿足（4q+1）-子集數(shù)大于頂點數(shù). 顯然當(dāng)q≥4時， （4q+2）lt;5

q， 矛盾. 下面構(gòu)造使用3種色的點被多重集可區(qū)別的一般全染色.

令A(yù)（5×q）=IqRq（1）Rq（1）

Rq（1）Lq（1，2）

Rq（1）IqRq（1）Rq（2）Lq（1，2）

Rq（1）Rq（1）IqLq（2，3）Rq（3）

Rq（1）Rq（2）Lq（2，3）IqRq（3）

Lq（1，2）Lq（1，2）Rq（3）R

q（3）Iq，（1）

用i/j表示Lq（i，j）， i，j∈{1，2，3}， k表示Rq（k）. 矩陣（1）的簡易寫法如下：

A（5×q）=Iq1111/21Iq121/211Iq2/33122/3Iq31/21/233Iq.

A（5×q）是5q×5q階矩陣， 將其分塊， 使得每塊都是q階方陣， 則分塊后的A（5×q）的主對角線的5塊都是Iq， 次對角線上的5塊從右上角到左下角分別是Lq（1，2），Rq（2），Iq，Rq（2），Lq（1，2）， 分塊后的A（5×q）次對角線上方且不在主對角線上的塊均為Rq（1）， 分塊后的A（5×q）位于第3行、 第4列相交處的塊為

Uq（2，3）， 位于第4行、 第3列相交處的塊為Uq（2，3）， 剩余塊均為Rq（3）.

分塊后的5q個行向量依次對應(yīng)到X1∪X2∪X3∪X4∪X5的5q個頂點上， 使得不同頂點對應(yīng)不同的行， 這些行是對應(yīng)頂點的色集合. 注意到， 當(dāng)k∈{1，2，3

，4，5}， l∈{1，2，…，q}時， A（5×q）的第（（k-1）q+l）列除0外的各元素構(gòu)成的多重集剛好是頂點x（k）l在f5×q下的多重色集合.

A（5×q）對應(yīng)K（5×q）的一個一般全染色f5×q. 下證該全染色是點可區(qū)別的.

① 同一部中點的色集合各不相同.

當(dāng)k∈{1，2，5}時， Xk中各頂點x（k）1，x（k）2，…，x（k）q的色集合（隨下標(biāo)的增大）含1的數(shù)目減少， 故Xk中任意兩個頂點可區(qū)別.

當(dāng)k∈{3，4}時， Xk中各頂點x（k）1，x（k）2，…，x（k）q的色集合（隨下標(biāo)的增大）含2的數(shù)目減少， 故Xk中任意兩個頂點可區(qū)別.

② 若兩個頂點屬于不同部， 則這兩個點的色集合不同.

X1∪X2中各頂點的色集合不含3， 而X3∪X4∪X5中各頂點的色集合均含3， 故X1∪X2中各頂點與X3∪X4∪X5中各頂點可區(qū)別.

對1≤klt;l≤2， Xl中各頂點的色集合含2的數(shù)目至少為q， Xk中各頂點的色集合含2的數(shù)目至多為（q-1）， 且（q-1）lt;q， 故Xk中各頂點與Xl中各頂點可區(qū)別.

對3≤klt;l≤4， Xl中各頂點的色集合含2的數(shù)目至少為（q+1）， Xk中各頂點的色集合含2的數(shù)目至多為q， 且qlt;（q+1）， 故Xk中各頂點與Xl中各頂點可區(qū)別.

當(dāng)k=5時， Xk中各頂點的色集合包含最少2q個3， X3∪X4中各頂點的色集合包含最多（2q-1）個3， 故X5中頂點與X3∪X4中頂點可區(qū)別. 即若兩個頂點屬于不同部， 則這兩個點的色集合不同.

2） 當(dāng)p=6， q≥4時， 圖G共有6q個頂點， 每個頂點的色集合對應(yīng)一個（5q+1）-子集.

首先證明圖G不存在使用2種色的點被多重集可區(qū)別的一般全染色. 用反證法， 假設(shè)圖G存在使用2種色的點被多重集可區(qū)別的一般全染色， 則由引理1可知， 2種色的（5q+1）-子集共

有（5q+2）個. 若使2種色可染， 則需滿足（5q+1）-子集數(shù)大于頂點數(shù). 顯然當(dāng)q≥4時， （5q+2）lt;6q， 矛盾. 下面構(gòu)造使用3種色的點被多重集可區(qū)別的一般全染色.

令M1=（Rq（1），Lq（1，2），Rq（2），Lq（2，3），Rq（3））， 該矩陣可寫成如下形式：

M1=1…11…12…22…23…3323

1…11222…22333…33.

q個" "q個" q個" q個" q個

M1是q×（5q+1）階矩陣， 將其分塊， 使得分塊后的q個行向量依次對

應(yīng)到X6的q個頂點上， 且不同頂點對應(yīng)不同的行， 這些行是對應(yīng)頂點的色集合.

下面對色集合進行分配， 當(dāng)l∈{1，2，3，4，5}時， 第l個塊中的（i，j）-元素（顏色）染邊x（6）ix（l）j， i，j∈{1，2，…，q}， 最后一列的q種顏色依次染X6中的q

個頂點x（6）1，x（6）2，…，x（6）q. 于是X6中的全體頂點和X6與X1∪X2∪X3∪X4∪X5中所有頂點的連邊已染完色.

令M2=（Lq（1，2），Rq（2），Lq（2，3），Rq（3），N），

該矩陣可寫成如下形式：

M2=1…12…22…23…33

231222…22333…33.

q個" q個" q個" q個

M2是q×（4q+1）階矩陣， 將其分塊， 使得分塊后的q個行向量依次對應(yīng)到X5的q個

頂點上， 且不同頂點對應(yīng)不同的行， 這些行是對應(yīng)頂點的色集合除（X5，X6）外的其他元素組成的色集合.

下面對色集合進行分配， 當(dāng)l∈{1，2，3，4}時， 第l塊中的（i，j）-元素（顏色）染邊x（5）ix（l）j， i，j∈{1，2，…，q}， 最后一列的q種顏色依次染X5中的q個頂點x（5）1，x（5）2，…，

x（5）q. 于是X5中的全體頂點和X5與X1∪X2∪X3∪X4中所有頂點的連邊已染完色.

令M3=（Lq（1，2），Rq（2），Lq（2，3），N）， 該矩陣可寫成如下形式：

M3=1…12…22…2323

1222…22333.

q個" q個" q個

M3是q×（3q+1）階矩陣， 將其分塊， 使得分塊后的q個行向量依次對應(yīng)到

X4的q個頂點上， 且不同頂點對應(yīng)不同的行， 這些行是對應(yīng)頂點的色集合除（X4，X5）和（X4，X6）外的其他元素組成的色集合.

下面對色集合進行分配， 當(dāng)l∈{1，2，3}時， 第l塊中的（i，j）-元素（顏色）染邊x（4）ix（l）j， i，j∈{

1，2，…，q}， 最后一列的q種顏色依次染X4中的q個頂點x（4）1，x（4）2，…，x（4）q. 于是X4中的全體頂點和X4與X1∪X2∪X3中所有頂點的連邊已染完色.

令M4=（Rq（1），Lq（1，2），N）， 該矩陣可寫成如下形式：

M4=1…11…1321…11223.

q個" q個

M4是q×（2q+1）階矩陣， 將其分塊， 使得分塊后的q個行向量依次對應(yīng)到X3的q個頂點上， 且不同頂點對應(yīng)不

同的行， 這些行是對應(yīng)頂點的色集合除（X3，X4），（X3，X5），（X3，X6）外的其他元素組成的色集合.

下面對色集合進行分配， 當(dāng)l∈{1，2}時， 第l塊中的（i，j）-元素（顏色）染邊x（3）ix（l）j， i，j∈{1，2，…，q}， 最后一列的q種顏色依次

染X3中的q個頂點x（3）1，x（3）2，…，x（3）q. 于是X3中的全體頂點和X3與X1∪X2中所有頂點的連邊已染完色.

最后將（X1，X2）的所有邊染色2， 將X1中全體頂點染色1， X2中全體頂點染色2. 于是圖G的

全體頂點和邊已染完色. 下面說明在這種染色方案下點被多重色集合可區(qū)別.

① 同一部中點的色集合各不相同.

當(dāng)k∈{1，2，3，4，5，6}時， Xk中各頂點x（k）1，x（k）2，…，x（k）q的色集合（隨下標(biāo)的增大）含1的數(shù)目減少， 故Xk中任意兩個頂點可區(qū)別.

② 若兩個頂點屬于不同部， 則這兩個點的色集合不同.

X6中各頂點的色集合包含3的數(shù)目最大值為2n（在（x（6）q）取得）， X5中各頂點的色集合包含3的數(shù)目最小值為2n+1（在（x（5）1）取得）， 故X

5中點與X6中點可區(qū)別. X5∪X6中頂點的色集合含2的最大值為2n（X5∪X6中頂點的色集合含2的數(shù)目相同）， X3∪X4中頂點的色集合

含2的最小值為2n+1（在（x（3）q）或（x（4）q）取得）， 故X3∪X4中點與X5∪X6中點可區(qū)別.

X3中頂點的色集合含1的數(shù)目最小值為n+1（在（x（3）q）取得）， X4中頂點的色集合含1的數(shù)目最大值為n（在（x（4）1）取得），

故X3中點與X4中點可區(qū)別. X1∪X2中每個點的色集合不含顏色3， 而X3∪X4∪X5∪X6中每個點的色集合均包含顏色3， 故X1∪X2中點與X3∪X4

∪X5∪X6中點可區(qū)別. X1中頂點的色集合含1的數(shù)目最小值為2n+3（在（x（1）q）取得）， X2中頂點的色集合含1的數(shù)目最大值為2n（在

（x（2）1）取得）， 故X1中點與X2中點可區(qū)別. 即若兩個頂點屬于不同部， 則這兩個點的色集合不同.

3） 當(dāng)p≥7， q≥4時， 圖G共有pq個頂點， 每個頂點的色集合對應(yīng)一個（（p-1）q+1）-子集.

首先證明圖G不存在使用2種色的點被多重集可區(qū)別的一般全染色. 用反證法， 假設(shè)圖G

存在使用2種色的點被多重集可區(qū)別的一般全染色， 則由引理1可知， 2種色的（（p-1）q+1）-子集共有（（p-1）q+2）個. 若使2種色可染， 則需滿足（（p-1）q+1）-子集數(shù)大于頂點數(shù). 顯然當(dāng)q≥4

時， （p-1）q+2lt;pq， 矛盾. 下面構(gòu)造使用3種色的點被多重集可區(qū)別的一般全染色.

情形① q≡1（mod 2）.

構(gòu)造一個pq×pq階矩陣A（p×q）=（M1，M2）， 其中

M1=IqRq（1）……Rq（1）Rq（1）

IqRq（1）…Rq（1）Rq（1）

Rq（1）Rq（1）Rq（1）IqRq（1）

Rq（1）IqRq（1）

Rq（1）Rq（2）Rq（1）Rq（2）Rq（2）Rq（1）Rq（2）…Rq（2）Rq（1）Rq（2）……Rq（2）Uq（1，2

）" …" …" …" Uq（1，2）（p-1）/2個，

M2=Rq（1）………Rq（1）Uq（1，2）

Rq（1）………Rq（2）Rq（1）…R

q（1）Rq（2）Rq（1）Rq（1）Rq（2）

Rq（1）Rq（2）Uq（1，2）

IqRq（2）Uq（2，3）Rq（2）I

qRq（2）Rq（2）Rq（2）Iq

Rq（2）Rq（2）Uq（2，3）Rq（2）…Rq（2）Uq（2，3）Rq（3）R

q（2）…Rq（2）Uq（2，3）IqRq（3）

Uq（2，3）…Uq（2，3）Rq（3）Rq（3）Iq.

（p-5）/2個

用Iq表示q階單位陣， 為方便， 在簡易寫法中用i/j表示Uq（i，j）， i，j∈{1，2，3}， 用k表示Rq

（k）， k∈{1，2，3}， 從而矩陣A（p×q）的簡易寫法為

A（p×q）=Iq1…11…111/21Iq…11…121/

211…Iq1

…221/211…1Iq…222/31

1…22…Iq2/3312…22…2/3Iq3

1/21/2…1/22/3…33Iq.

（p-1）/2個（p-5）/2個

A（p×q）是pq×pq階方陣， 將其分塊， 使得分塊后的每塊都是q階方陣， 則分塊后的A（p×q）次對角線上的p個塊從右上角到左下角分別是Uq（1，2），Rq（2），…，Rq（2）（p-3）/2個，Iq，Rq（2），…，Rq（2）（p-3）/2個，Uq（1，2）.

A（p×q）主對角線的p個塊都是Iq， 分塊后的第p行（最后1行）的p

個塊依次是Uq（1，2），…，Uq（1，2）（p-1）/2個，Uq（2，3）

，…，Uq（2，3）（p-5）/2個，Rq（3），Rq（3），Iq.

分塊后的A（p×q）次對角線上方的不在主對角線上的塊均為Rq（1）， 分塊后位于第（p-1）行、 第（p-2）列相交處的

塊為Uq（2，3）， 位于第（p-2）行、 第（p-1）列相交處的塊為Uq（2，3）， 分塊后A（p×q）中其他位于次對角線下方， 但不在主對角線上， 且不在

第p行和第p列， 不是第（p-1）行、 第（p-2）列相交處的塊， 也不是第（p-2）行、 第（p-1）列相交處的塊均為Rq（2）. 例如， A（11×q）為如下方陣（這里給出簡易寫法）：

A（11×q）=Iq111111111

1/21Iq111111121/211Iq11111221/2111Iq1112221/2

1111Iq122221/211111Iq22222/3

111122Iq2222/31112222Iq222/311222222Iq2/33122222222/3Iq

31/21/21/21/21/22/32/32/333Iq.

A（p×q）對應(yīng)K（p×q）的一個一般全染色fp×q. 下證該全染色是點可區(qū)別的.

注意到當(dāng)k∈{1，2，…，p}， l∈{1，2，…，q}時， A（p×q）的第（（k-1）q+l）列除0外的各元素構(gòu)成的多重集剛好是頂點x（k）l在fp×q下的多重色集合.

（i） 同一部中點的色集合各不相同.

當(dāng)k∈1，2，…，p-12時， Xk中各頂點x（k）1，x（k）2，…，x（k）q的色集合（隨下標(biāo)的增大）含1的數(shù)目減少， 故Xk

中任意兩個頂點可區(qū)別. 當(dāng)k∈p+12，p+32，…，p時， X

k中各頂點x（k）1，x（k）2，…，x（k）q的色集合（隨下標(biāo)的增大）含2的數(shù)目減少， 故Xk中任意兩個頂點可區(qū)別.

（ii） 若兩個頂點屬于不同部， 則這兩個點的色集合不同.

X1∪X2∪…∪X（p-1）/2中各頂點的色集合不含3， 而X（p+1）/2∪X（p+3）/2∪…∪Xp中各頂點的色集合均

含3， 故X1∪X2∪…∪X（p-1）/2中各頂點與X（p+1）/2∪X（p+3）/2∪…∪Xp中各頂點可區(qū)別.

對1≤klt;l≤p-12， Xl中各頂點的色集合含2的數(shù)目比Xk中各頂點的色集合含2的數(shù)目多， 且差值至少為q（Xk與Xl為相鄰遞增部時取得）， 故Xk中各頂點與Xl中各頂點可區(qū)別.

對p+12≤klt;l≤p-1， Xl中各頂點的色集合含1的數(shù)目比Xk中各頂點的色集合含1的數(shù)目少， 且差值至少為q（Xk與Xl為相鄰遞增部時取得）

， 故Xk中各頂點與Xl中各頂點可區(qū)別. 當(dāng)k∈p+12，p+32，…，p-1時，

Xk中各頂點的色集合包含最多2q個3， Xp中各頂點的色集合包含最少（2q+1）個3，" 故Xk中的點與Xp中的點可區(qū)別. 即若兩個頂點屬于不同部， 則這兩個點的色集合不同.

情形② q≡0（mod 2）.

構(gòu)造一個pq×pq階矩陣A（p×q）=（M3，M4）， 其中

M3=IqRq（1）………Rq（1）Rq（

1）IqRq（1）……Rq（1）Rq（1）

IqRq（1）…Rq（1）Rq（1）Iq

Rq（1）Rq（1）Rq（1）IqRq

（1）Rq（1）Iq

Rq（1）Rq（2）Rq（1）Rq（2）R

q（2）Rq（1）Rq（2）…Rq（2）R

q（1）Rq（2）……Rq（2）R

q（1）Rq（2）………Rq（2）

Uq（1，2）…………Uq（1，2），

p/2個

M4=Rq（1）………Rq（1）

Uq（1，2）Rq（1）……Rq（1）Rq（2）

Rq（1）…Rq（1）Rq（2）Rq（1）R

q（1）Rq（2）Rq（1）Rq（2）

Rq（2）Uq（1，2）IqRq（2）Uq（2，3）Rq（2）IqR

q（2）Rq（2）Rq（2）IqRq（2）

Rq（2）Uq（2，3）Rq（2）…Rq（2）Iq

Uq（2，3）Rq（3）Rq（2）…Rq（2）Uq（2，3）IqRq（3）

Uq（2，3）…Uq（2，3）Rq（3）Rq（3）Iq.

（p-6）/2個

用Iq表示q階單位陣， 用i/j表示Uq（i，j）， i，j∈{1，2，3}， k表示Rq（k）， k∈{1，2，3}. 矩陣A（p×q）的簡易寫法為

A（p×q）=Iq11…111…1111/21Iq1…111…1121/211Iq…111

…1221/2111…Iq11

…2221/2111…1Iq2…2221/2111…12Iq…2222/3111…222…

Iq222/3112…222…2Iq23122…222…22/3Iq3

1/21/21/2…1/21/22/3…2/333Iq.

p/2個""" （p-6）/2個

A（p×q）是pq×pq階方陣， 將其分塊， 使得分塊后的每塊都是q階方陣， 且分塊后的A（p×q）次對角線上的p個塊從右上角到左下角分別是Uq（1，2），Rq（2），…，Rq（2）（p-2）/2個，Rq（2），…，Rq（2）

（p-2）/2個，Uq（1，2）. A（p×q）的主對角線上p個塊都是Iq， 分塊后第p行（最

后1行）的p個塊依次是Uq（1，2），…，Uq（1，2）p/2個，Uq（2，3），…，Uq（2，3）

（p-6）/2個，Rq（3），Rq（3），Iq. 分塊后的A（p×q）次對角線上方不

在主對角線上的塊均為Rq（1）， 分塊后的A（p×q）中位于第（p-1）行、 第（p-2）列相交處的塊為Uq（2，3）， 位于第（p-2）行、 第（p-1）列相交

處的塊為Uq（2，3）， 分塊后A（p×q）中其他位于次對角線下方， 但不在主對角線上， 且不在第p行和第p列， 不是第（p-1）行、 第（p-2）列相交處的塊， 也不是第（p-2）行

、 第（p-1）列相交處的塊均為Rq（2）. 例如， A（12×q）即為如下方陣（簡易寫法）：

A（12×q）=Iq11111

111111/21Iq1111111111/211Iq11111

1121/2111Iq11111221/21111Iq1112

221/211111Iq122221/2111111Iq2

2222/31111122Iq2222/311112222Iq222/3111222222I

q2/331122222222/3Iq31/21/2

1/21/21/21/22/32/32/333Iq.

A（p×q）對應(yīng)K（p×q）的一個一般全染色fp×q. 下證該全染色是點可區(qū)別的.

注意到當(dāng)k∈{1，2，…，p}， l∈{1，2，…，q}時， A（p×q）的第（（k-1）q+l）列中除0外的各元素構(gòu)成的多重集剛好是頂點x（k）l在fp×q下的多重色集合.

（i） 同一部中點的色集合各不相同.

當(dāng)k∈1，2，…，p2時， Xk中各頂點x（k）1，x（k）2，…，x（k）q的色集合（隨下標(biāo)的增大）含1的數(shù)目減少， 故Xk

中任意兩個頂點可區(qū)別. 當(dāng)k∈p+22，p+42，…，p時， Xk

中各頂點x（k）1，x（k）2，…，x（k）q的色集合（隨下標(biāo)的增大）含2的數(shù)目減少， 故Xk中任意兩個頂點可區(qū)別.

（ii） 若兩個頂點屬于不同部， 則這兩個點的色集合不同.

X1∪X2∪…∪Xp/2中各頂點的色集合不含3， 而X（p+2）/2∪X（p+4）/2∪…∪Xp中各頂點的色集合均含3，

故X1∪X2∪…∪Xp/2中各頂點與X（p+2）/2∪X（p+4）/2∪…∪Xp中各頂點可區(qū)別.

當(dāng)1≤klt;l≤p2時， Xl中各頂點的色集合含2的數(shù)目比Xk中各頂點的色集合含2的數(shù)目多， 且差值至少為q（Xk與Xl為相鄰遞增部時取得）

， 故Xk中各頂點與Xl中各頂點可區(qū)別. 當(dāng)p+22≤klt;l≤p-1時， Xl中各頂點的色集合

含1的數(shù)目比Xk中各頂點的色集合含1的數(shù)目少， 且差值至少為q（Xk與Xl為相鄰遞增部時取得）， 故Xk中各頂點與Xl中各頂點可區(qū)別. 當(dāng)k∈p+22，p+42，…，p-1時， Xk中各頂點的色集合包含最多2q個3， Xk中各頂點的色集合包含最少（2q+1）個3， 故Xk中各頂點與Xp

中各頂點可區(qū)別. 即若兩個頂點屬于不同部， 則這兩個點的色集合不同.

參考文獻

［1］" HARARY F， PLANTHOLT M. The Point-Distinguishing Chromatic Index ［C］//G

raphs and Application， Proceedings of the First Colorado Symposium on Graph Theory. New York： Wiley Interscience， 1985： 147-162.

［2］" LIU C J， ZHU E Q. General Vertex-Distinguishing Total Coloring of Graphs ［

J/OL］. Journal of Applied Mathematics， （2014-08-03）［2023-03-21］. http：//doi.org/10.1155/2014/849748.

［3］" 陳祥恩， 張爽， 李澤鵬. K2，4，p的點可區(qū)別IE-全染色 ［J］. 電子與信

息學(xué)報， 2020， 42（12）： 2999-3004. （CHEN X E， ZHANG S， LI Z P. Vertex Distinguis

hed IE-Total Coloring of K2，4，p［J］. Journal of Electronics amp; Information Technology， 2020， 42（12）： 2999-3004.）

［4］" 陳祥恩， 王勇軍. 完全二部圖的點被多重集可區(qū)別的IE-全染色及一般全染色 ［J］. 吉

林大學(xué)學(xué)報（理學(xué)版）， 2022， 60（4）： 838-844. （CHEN X E， WANG Y J. IE-Total Colori

ng and General Total Coloring of Complete Bipartite Graph Which Are Vertex-Distinguished by Multiple Sets ［J］. Journal of Jilin University （Science Edition）， 2022， 60（4）： 838-844.）

［5］" 王勇軍， 陳祥恩. 完全四部圖Kn1，n2，n3，n4的點被多重集可區(qū)別的一般全染色（n1≤n2=n3lt;n4或n1=n2=n3=n4） ［J］.

吉林大學(xué)學(xué)報（理學(xué)版）， 2023， 61（5）： 1037-1041. （WANG Y J， CHEN X E. Vertex Distinguishing Gener

al Total Colorings of Complete 4-Partite Graphs Kn1，n2，n3，n4 by M

ultisets （n1≤n2=n3lt;n4 or n1=n2=n3=n4） ［J］. Journal of Jilin University （Science Edition）， 2023， 61（5）： 1037-1041.）

［6］" 王勇軍， 陳祥恩. 完全三部圖的點被多重集可區(qū)別的一般全染色 ［J/OL］. 山東大學(xué)學(xué)報（理學(xué)版）， （2023-09-20）［2023-12-24］. doi：10.6040/j.

issn.1671-9352.0.2022.667. （WANG Y J， CHEN X E. Vertex Distinguishing General Total Colorings of Complete 3-Partite Graphs by Multisets ［J/OL］. Journal of S

handong University （Science Edition）， （2023-09-20）［2023-12-24］. doi：10.6040/j.issn.1671-9352.0.2022.667.）

［7］" 陳祥恩. 某些頂點對被非多重色集合所區(qū)別的未必正常染色的綜述 ［J］. 廣州大學(xué)學(xué)報（自然科學(xué)版）， 2019， 18（4）： 50-59. （CHEN X E. A Survey

on Not Necessarily Proper Colorings under Which Certain Pairs of Vertices Are Distinguished by Nonmultiple Color Sets ［J］. Journal of Gua

ngzhou University （Natural Science Edition）， 2019， 18（4）： 50-59.）

［8］" 邵嘉裕. 組合數(shù)學(xué) ［M］. 上海： 同濟大學(xué)出版社， 1991： 5-14. （SH

AO J Y. Combinatorial Mathematics ［M］. Shanghai： Tongji University Press， 1991： 5-14.）

（責(zé)任編輯： 李" 琦）