等完全p-部圖的點被多重集可區別的一般全染色

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

關鍵詞： 等完全p-部圖; 一般全染色; 多重集; 色集合; 可區別

中圖分類號： O157.5" 文獻標志碼： 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—）， 女， 漢族， 碩士研究生， 從事圖論及其應用的研究， E-mail： wangxuan20220901@163.com. 通信作者簡介：

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

基金項目： 國家自然科學基金（批準號： 11761064）.

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

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

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

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

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

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

多重集可區別的一般全色數.

1" 預備知識

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

種顏色的一般全染色稱為圖G的k-一般全染色. 設f為圖G的一般全染色， 對任意的x∈V（G）， 用f（x）或（x）表示點x的色以及與x關聯的邊的顏色構成的多重集.

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

， 則稱f是點被多重集可區別的.

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

用K（p×q）表示每個部中頂點數目均為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.

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

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

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

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

2" 主要結果

定理1" 當p≥2， q=1時， χgvt（G）=2.

證明： 當p≥2， q=1時， 圖G為p階完全圖Kp， 構造一個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使用兩種顏色的點可區別一般全染色Fig.1" Vertex-distinguishing general totalcolorings with two colors of K6

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

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

圖G為6階完全圖K6， 構造一個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" 當p≥2， q=2時， χgvt（G）=2.

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

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

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

到Ap-1止， 多重集Ai所含2的數目嚴格遞增， Ai中元素按從大到小的順序排列， 1≤i≤p-1. 例如， 當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對應的（2p-1）-子集（多重集）中的元素1，2對調， 所得新的多重集記為du（Ai）， du（Ai）中含元素1的個數等于i（i=0，1，…，p-1）. 多重集du（

A0），du（A1），…，du（Ap-1）中所含元素1的數目嚴格遞增， du（Ai）中元素按從小到大的順序排列， 0≤i≤p-1. 例如， 當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依次分別對應到x（1）1，x（2）1，x（3）1，…，x（p）1， 將du（A0），du（A1），du（A2），…，

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

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

顏色1， x（2）2未被染色的關聯邊都染顏色2. 將x（3）1未被染色的關聯邊都染顏色1， x（3）2未被染色的關聯邊都染顏色2. 依次類推， 直到最后將

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

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

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

圖2" K（6×2）的點被多重集可區別的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" 當p≥2， q=3時， χgvt（G）=3.

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

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

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

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

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

的數目隨上標的增大逐次遞減. 例如， 當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}

均是對應部所有多重集中含1數目最多的色集.

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

的數目隨上標的增大逐次遞減. 例如， 當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}

均是對應部所有多重集中含2數目最多的色集合.

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

的數目隨上標的增大逐次遞減. 例如， 當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}

均是對應部所有多重集中含3數目最多的色集合.

將（x（1）1），（x（2）1），…，（x（p）1）對應到頂點x（1）1，x（2）1，…，x（p）1， 將（x（1）2）

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

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

）3的所有關聯邊均染顏色3. 令x（2）1未被染色的關聯邊均染顏色1， x（2）2未被染色的關聯邊均染顏色2， x（2）3未被染色的關聯邊均染顏色3. 依次類推，

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

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

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

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

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

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

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

∪Xp中點與x（j）1所連色為1的邊的條數. 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的邊的條數比x（j）1與Xi+1∪…∪Xj-1中點所連色為1的邊的條數多， x（i）1與Xj中各點連邊的色均為1（共3條），

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

）含2的數目多， （x（i）3）含3的數目比（x（j）3）含3的數目多.

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

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

目多. 從而x（i）2與x（j）1，x（j）3可區別. （x（i）3）含3的數目多于（x（j）3）含3的數目， 即x（i）3與x（j）3可區別，

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

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

而（x（j）3）含

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

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

例如， K（3×3）的點被多重集可區別的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" 當p≥5， q≥4時， χgvt（G）=3.

證明： 對于等完全p-部圖K（p×q）， 其第i個部全體頂點構成的集合為Xi， i=1，2，…，p. 設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個頂點的邊的顏色，

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

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

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

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

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

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

令A（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個行向量依次對應到X1∪X2∪X3∪X4∪X5的5q個頂點上， 使得不同頂點對應不同的行， 這些行是對應頂點的色集合. 注意到， 當k∈{1，2，3

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

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

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

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

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

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

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

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

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

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

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

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

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

令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個行向量依次對

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

下面對色集合進行分配， 當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個行向量依次對應到X5的q個

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

下面對色集合進行分配， 當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個行向量依次對應到

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

下面對色集合進行分配， 當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個行向量依次對應到X3的q個頂點上， 且不同頂點對應不

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

下面對色集合進行分配， 當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的

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

情形① q≡1（mod 2）.

構造一個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）對應K（p×q）的一個一般全染色fp×q. 下證該全染色是點可區別的.

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

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

當k∈1，2，…，p-12時， Xk中各頂點x（k）1，x（k）2，…，x（k）q的色集合（隨下標的增大）含1的數目減少， 故Xk

中任意兩個頂點可區別. 當k∈p+12，p+32，…，p時， X

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

（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中各頂點可區別.

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

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

， 故Xk中各頂點與Xl中各頂點可區別. 當k∈p+12，p+32，…，p-1時，

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

情形② q≡0（mod 2）.

構造一個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）對應K（p×q）的一個一般全染色fp×q. 下證該全染色是點可區別的.

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

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

當k∈1，2，…，p2時， Xk中各頂點x（k）1，x（k）2，…，x（k）q的色集合（隨下標的增大）含1的數目減少， 故Xk

中任意兩個頂點可區別. 當k∈p+22，p+42，…，p時， Xk

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

（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中各頂點可區別.

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

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

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

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

參考文獻

［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的點可區別IE-全染色 ［J］. 電子與信

息學報， 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］" 陳祥恩， 王勇軍. 完全二部圖的點被多重集可區別的IE-全染色及一般全染色 ［J］. 吉

林大學學報（理學版）， 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的點被多重集可區別的一般全染色（n1≤n2=n3lt;n4或n1=n2=n3=n4） ［J］.

吉林大學學報（理學版）， 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］" 王勇軍， 陳祥恩. 完全三部圖的點被多重集可區別的一般全染色 ［J/OL］. 山東大學學報（理學版）， （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］" 陳祥恩. 某些頂點對被非多重色集合所區別的未必正常染色的綜述 ［J］. 廣州大學學報（自然科學版）， 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］" 邵嘉裕. 組合數學 ［M］. 上海： 同濟大學出版社， 1991： 5-14. （SH

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

（責任編輯： 李" 琦）