完全二部圖K4,n的點(diǎn)被多重集可區(qū)別的E-全染色

摘要： 利用反證法、 色集合事先分配法及構(gòu)造具體染色等方法， 討論完全二部圖K4，n的點(diǎn)被多重集可區(qū)別的E-全染色， 并確定K4，n的點(diǎn)被多重集可區(qū)別的E-全色數(shù).

關(guān)鍵詞： 完全二部圖; E-全染色; E-全色數(shù); 多重集; 色集合

中圖分類號(hào)： O157.5" 文獻(xiàn)標(biāo)志碼： A" 文章編號(hào)： 1671-5489（2024）03-0480-07

E-Total Coloring of" Complete Bipartite Graphs K4，n Which Are Vertex-Distinguished by Multiple Sets

GUO Yaqin， CHEN Xiang’en

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

Abstract： We discussed the E-total coloring of complete bipartite graphs K4，n which were vertex-distinguished by multiple sets by using

the method of proof by contradiction， the method of pre-assignment of color sets and the method of constructing specific coloring， and determined

E＼|total chromatic numbers of K4，n which were vertex-distinguished by multiple sets.

Keywords： complete bipartite graph; E-total coloring; E-total chromatic number; multiple set; color set

收稿日期： 2023-10-07.

第一作者簡(jiǎn)介： 郭亞勤（1998—）， 女， 漢族， 碩士研究生， 從事圖論及其應(yīng)用的研究， E-mail： guoyaqin20220901@163.com. 通信作者簡(jiǎn)介

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

基金項(xiàng)目： 國(guó)家自然科學(xué)基金（批準(zhǔn)號(hào)： 11761064）.

目前， 關(guān)于圖的點(diǎn)可區(qū)別全染色［1］問題已有很多研究成果. 例如： Chen等［2］提出了圖的點(diǎn)可區(qū)別E-全染色; 文獻(xiàn)［3-6］研究了完全二部圖的點(diǎn)可區(qū)別E-全染色；

文獻(xiàn)［7］綜述了任意兩個(gè)不同頂點(diǎn)（或任意兩個(gè)相鄰頂點(diǎn)， 或任意兩個(gè)距離不超過d的不同頂點(diǎn)）被非多重色集合可區(qū)別的一般邊染色（分別為V-全染色、 I-全染色、 E-全染色

、 VI-全染色、 VE-全染色、 IE-全染色、 一般全染色）的研究進(jìn)展; 文獻(xiàn)［8-9］探討了圈與路、 輪與扇的點(diǎn)被多重集可區(qū)別的E-全染色， 并給出了圈與路、 輪與扇的頂

點(diǎn)被多重集可區(qū)別的E-全染色方案， 構(gòu)造了圈和輪的點(diǎn)被多重集可區(qū)別的E-全染色算法.

本文討論完全二部圖K4，n的點(diǎn)被多重集可區(qū)別的E-全染色， 并確定該類圖的點(diǎn)被多重集可區(qū)別的E-全色數(shù).

1" 預(yù)備知識(shí)

圖G的一個(gè)E-全染色是指用若干種顏色對(duì)圖G的頂點(diǎn)和邊的一個(gè)分配， 使得任意相鄰的頂點(diǎn)被分配不同的顏色， 且每條邊與關(guān)聯(lián)的點(diǎn)被分配不同的顏色.

設(shè)f是圖G的一個(gè)E-全染色， x是圖G的任意一個(gè)頂點(diǎn)， 在f下點(diǎn)x的顏色以及與點(diǎn)x關(guān)聯(lián)邊的顏色構(gòu)成的（多重）集合稱為點(diǎn)x在f下的（多重）色集合， 記為f（x）或者（x）.

設(shè)f是圖G的E-全染色， 且對(duì)任意u，v∈V（G）， 當(dāng)u≠v時(shí)， 有（u）≠（v）， 則稱f是點(diǎn)被多重集可區(qū)別的.

對(duì)圖G進(jìn)行點(diǎn)被多重集可區(qū)別的E-全染色所需最少的顏色數(shù)目， 稱為圖G的點(diǎn)被多重集可區(qū)別的E-全色數(shù)， 記為χevt（G）， 即

χevt（G）=min{k圖G存在可用顏色有k種的點(diǎn)被多重集可區(qū)別的E-全染色}.

本文用Km，n表示完全二部圖， 其中

V（Km，n）={u1，u2，…，um，v1，v2，…，vn}=X∪Y，X={u1，u2，…，um}，" Y={v1，v2，…，vn}，

E（Km，n）={uivji=1，2，…，m; j=1，2，…，n}.

定義映射h： V∪E→{1，2，…，k}， 通常情況下在進(jìn)行染色時(shí)， 所用的k種顏色用{1，2，…，k}表示. l-E-全染色是指可用的顏色有l(wèi)種的E-全染色， 可用的顏色有l(wèi)種的點(diǎn)被多

重集可區(qū)別的E-全染色稱為點(diǎn)被多重集可區(qū)別的l-E-全染色， 其中l(wèi)∈{1，2，…，k}.

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

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

引理2［10］" nr=n-1r+n-1r-1.

引理3" 若完全二部圖K4，n存在可用的顏色有l(wèi)種的點(diǎn)被多重集可區(qū)別的E-全染色g， 則Y中頂點(diǎn)在g下的色集合是{1，2，…，l}

的5-子集， 且至少有一種顏色在該5-子集中只出現(xiàn)一次.

證明： 對(duì)Y中的任意一點(diǎn)v， 在g下點(diǎn)v的多重色集合中， 給點(diǎn)v染的顏色在該多重色集合中只出現(xiàn)一次， 所以該多重色集合是{1，2，…，l}的5-子集， 且至少有一種顏色在該5-子集中只出現(xiàn)一次.

2" 主要結(jié)果

定理1" 若4≤n≤16， 則χevt（K4，n）=4.

證明： 先證K4，n不存在可用顏色有3種的點(diǎn)被多重集可區(qū)別的E-全染色. 假設(shè)K4，n存在可用的顏色有3種的點(diǎn)被多重集可區(qū)別的E-全

染色h， 則頂點(diǎn)在h下的色集合為{1，2，3}的5-子集， 且至少有一種顏色在該5-子集中只出現(xiàn)一次， 這樣的5-子集有{1，2，2，3，3}，{2，1，1，3，3}，{3，1，1，2，2}，{1

，2，3，3，3}，{1，3，2，2，2}，{3，2，1，1，1}，{1，2，2，2，2}，{1，3，3，3，3}，{2，3，3，3，3}，{2，1，1，1，1}，{3，1，1，1，1}，{3，2，2，2，2}. 下面分4種情形討論.

情形1） h（u1）=h（u2）=h（u3）=h（u4）.

不妨設(shè)h（u1）=h（u2）=h（u3）=h（u4）=1. 此時(shí)K4，n的所有邊及Y中的所有頂點(diǎn)都不能染顏色1， 故Y中的每個(gè)頂點(diǎn)在h下的色集合是{1，2，3}的5-子集， 且至少有一種顏色在該5-子集中只出現(xiàn)

一次， 這樣的5-子集只有{2，3，3，3，3}，{3，2，2，2，2}. 由于4≤n≤16， 因此這兩個(gè)5-子集不能區(qū)分Y中的n個(gè)頂點(diǎn)， 矛盾.

情形2） h（u1）=h（u2）=h（u3）≠h（u4）.

不妨設(shè)h（u1）=h（u2）=h（u3）=1， h（u4）=2. 此時(shí)Y中的所有頂點(diǎn)都不能染顏色1，2， 故Y中的每個(gè)頂點(diǎn)在h下的

色集合是{1，2，3}的5-子集， 且至少有一種顏色在該5-子集中只出現(xiàn)一次， 這樣的5-子集只有{3，1，2，2，2}. 由于4≤n≤16， 因此這個(gè)5-子集不能區(qū)分Y中的n個(gè)頂點(diǎn)， 矛盾.

情形3） h（u1）=h（u2）≠h（u3）=h（u4）.

不妨設(shè)h（u1）=h（u2）=1， h（u3）=h（u4）=2. 此時(shí)Y中的所有頂點(diǎn)都不能染顏色1，2， 故Y中的每個(gè)頂點(diǎn)在h下的色集合是{1，2，3}的5-子集， 且至少

有一種顏色在該5-子集中只出現(xiàn)一次， 這樣的5-子集只有{3，1，1，2，2}. 由于4≤n≤16， 因此這個(gè)5-子集不能區(qū)分Y中的n個(gè)頂點(diǎn)， 矛盾.

情形4） h（u1）=h（u2）≠h（u3）≠h（u4）且h（u1）=h（u2）≠h（u4）.

不妨設(shè)h（u1）=h（u2）=1， h（u3）=2， h（u4）=3. 此時(shí)Y中的所有頂點(diǎn)都不能染顏色1，2，3， 矛盾.

下證K4，n存在可用顏色有4種的點(diǎn)被多重集可區(qū)別的E-全染色. 不妨給X中的頂點(diǎn)u1，u2，u3，u4分別染顏色1，1，2，2， 下面利用如下5行、 17列的矩陣給出具體的染色方案：

034343334444433431422242222332423

4123234222233344342111314113133443

424141141131131434.

先將該矩陣中的第1行元素（顏色）除0外， 依次分配給Y中頂點(diǎn)v1，v2，…，v16， 將該矩陣的第1列元素（顏色）除0外， 依次分配給X中的頂點(diǎn)u1，u2，u

3，u4， 再將第（i+1）行、 第（j+1）列處的元素（顏色）分配給邊uivj（i=1，2，3，4， j=1，2，…，16）， 則第2行、 第3行、 第4行、 第5行恰好是X中的頂點(diǎn)u1，u

2，u3，u4對(duì)應(yīng)的色集合， 第2列、 第3列、 …、 第17列恰好是Y中頂點(diǎn)v1，v2，…，v16對(duì)應(yīng)的色集合.

由該矩陣可得： 當(dāng)n=4時(shí)， K4，4中的頂點(diǎn)在f下對(duì)應(yīng)的色集合均為5-子集，" X中的頂點(diǎn)在f下對(duì)應(yīng)的5-子集分別為{1，4，2，2，2}，{1，2，3，2，3}，{2，1，1，1，3}，{2，4，1，4

，1}， Y中的頂點(diǎn)在f下對(duì)應(yīng)的5-子集分別為{3，4，2，1，4}，{4，2，3，1，1}，{3，2，2，1，4}，{4，2，3，3，1}， 在f下X中所有的5-子集與Y中所有的5-子集互不相同， 故χevt（K4，4）=4；

當(dāng)5≤n≤16時(shí)， X中的頂點(diǎn)在f下對(duì)應(yīng)的色集合均為（n+1）-子集，" Y中的頂點(diǎn)對(duì)應(yīng)的色集合均為5-子集， 因此X中的頂點(diǎn)在f下對(duì)應(yīng)的色集合與Y中的頂

點(diǎn)在f下對(duì)應(yīng)的色集合互不相同. 按照該矩陣給出的具體染色方案， 對(duì)K4，n中的頂點(diǎn)及所有邊進(jìn)行染色， 可得X中的頂點(diǎn)在f下對(duì)應(yīng)的色集合互不相同， Y中的頂點(diǎn)

在f下對(duì)應(yīng)的色集合互不相同， 故χevt（K4，n）=4. 于是可得K4，n的點(diǎn)被多重集可區(qū)別的4＼|E-全染色.

定理2" 若k+25+k+14+k-23

-3k-22-5k+13lt;n≤k+35+k+24

+k-13-3k-12-5k+8， k≥5， 則χevt（K4，n）=k.

證明： 先證K4，n不存在可用顏色有（k-1）種的點(diǎn)被多重集可區(qū)別的E-全染色. 假設(shè)K4，n存在可用的顏色有（k-1）種的點(diǎn)被多重集可區(qū)別的E-全染色h， 下面分5種情形討論.

情形1） h（u1）=h（u2）=h（u3）=h（u4）.

不妨設(shè)h（u1）=h（u2）=h（u3）=h（u4）=1. 此時(shí)K4，n的所有邊及Y中的所有頂點(diǎn)都不能染顏色1， 故Y中的每個(gè)頂點(diǎn)在h下的色集合是{2，3，…，k-1}的5-子集，

且至少有一種顏色在該5-子集中只出現(xiàn)一次， 這樣的5-子集個(gè)數(shù)為

k-25+4k-24+6k-23+2k-22

=k+15+k4+k-23，

因此

k+15+" k4+k-23

-k+25+k+14+k-23-3

k-22+5k-13=" -k4-2k3+49k2-70k-9624.

當(dāng)k≥5時(shí)， -k4-2k3+49k2-70k-9624lt;0， 從而

k+15+k4+k-23

lt;k+25+k+14+k-23-3k-22-5k+13lt;n.

故所有這樣的5-子集不能區(qū)分Y中的n個(gè)頂點(diǎn)， 矛盾.

情形2） h（u1）=h（u2）=h（u3）≠h（u4）.

不妨設(shè)h（u1）=h（u2）=h（u3）=1， h（u4）=2. 此時(shí)， 對(duì)每個(gè)s，t，r∈{3，4，…，k-1}， x，y∈{1，2}， {x，s，s，s，s}，{s，x，x，x，x}，{x，y，y，y，y}，{s，1，1，1，2}，{s，1，1，1，t}，

{s，1，1，t，t}，{s，1，1，2，2}，{s，1，1，2，t}，{s，1，1，t，r}，{x，y，y，s，s}，{x，s，s，t，t}，{x，y，s，s，s}均不是Y中頂點(diǎn)的色集合， 故不能成為Y中頂點(diǎn)色集合的5-子集的個(gè)數(shù)為

21k-31+" 21k-31

+222+k-31+k-32+2k-32

+k-31+k-32+" k-33+222k-31

+21k-32+22k-31

=" k-13+4k-22+4k-31+2，

能成為Y中頂點(diǎn)色集合的5-子集的個(gè)數(shù)為

k-15+" 4k-14+3k-13+3k-13

+2k-12-k-13-4k-22-4k-31

-2=" k+25+k+14-4k-22-4k+10.

因此

k+25+" k+14-4k-22-4k+10-

k+25+k+14+k-23

-3k-22-5k+13=-k3+6k2-5k-126.

當(dāng)k≥5時(shí)， -k3+6k2-5k-126lt;0， 從而

k+25+" k+14-4k-22-4k+10lt;

k+25+k+14+k-23-3k-22-5k+13lt;n.

故所有這樣的5-子集不能區(qū)分Y中的n個(gè)頂點(diǎn)， 矛盾.

情形3） h（u1）=h（u2）≠h（u3）=h（u4）.

不妨設(shè)h（u1）=h（u2）=1， h（u3）=h（u4）=2. 此時(shí)， 對(duì)每個(gè)s，t∈{3，4，…，k-1}， x，y∈{1，2}， {x，y，y，s，s}，{x，s，s，t，t}，{x，y，s，s，s}，{x，s，y，y，y}，{s，t，x，x，x}，{x

，s，s，s，s}，{s，x，x，x，x}，{x，y，y，y，y}均不是Y中頂點(diǎn)的色集合， 故不能成為Y中頂點(diǎn)色集合的5-子集的個(gè)數(shù)為

222k-31+" 21k-32

+22k-31+222k-31

+21k-32+

21k-31

+21k-31+222

=4k-22+5k-31+2，

能成為Y中頂點(diǎn)色集合的5-子集的個(gè)數(shù)為

k-15+" 4k-14+3k-13+3k-13

+2k-12-4k-22+5k-31+2

=" k+25+k+14+k-23-3k-22-5k+13.

當(dāng)k≥5時(shí)，

k+25+k+14+k-23-3k-22-5k+13lt;n.

故所有這樣的5-子集不能區(qū)分Y中的n個(gè)頂點(diǎn)， 矛盾.

情形4） h（u1）=h（u2）≠h（u3）≠h（u4）且h（u1）=h（u2）≠h（u4）.

不妨設(shè)h（u1）=h（u2）=1， h（u3）=2， h（u4）=3. 此時(shí)， 對(duì)每個(gè)s，t∈{4，5，…，k-1}， x，y，z∈{1，2，3}， {x，y，z，s，s}，{x，y，y，z，z}，{x，y，y，s，s}，{x，s，s，t，t}，{2，s，1，1，1}，{3，s，1，1，1}，{s，t，

1，1，1}，{x，y，z，z，z}，{x，y，s，s，s}，{x，y，y，y，y}，{x，s，s，s，s}，{s，x，x，x，x}均不是Y中頂點(diǎn)的色集合， 故不能成為Y中頂點(diǎn)色集合的5-子集的個(gè)數(shù)為

33k-41+" 333+232k-41

+31k-42+k-41+k-41

+k-42+333+" 32k-41

+232+31k-41+31k-41

=4k-32+14k-41+12，

能成為Y中頂點(diǎn)色集合的5-子集的個(gè)數(shù)為

k-15+" 4k-14+3k-13+3k-13

+2k-12-4k-32+14k-41+12

=" k+25+k+14+k-13-4k-32-14k+44.

因此

k+25+" k+14+k-13-4k-32-14k+

44-" k+25+k+14+k-23

-3k-22-5k+13 =-5k+19.

當(dāng)k≥5時(shí)， -5k+19lt;0， 從而

k+25+" k+14+k-13-4k-32

-14k+44lt;" k+25+k+14+k-23-3k-22-5k+13lt;n.

故所有這樣的5-子集不能區(qū)分Y中的n個(gè)頂點(diǎn)， 矛盾.

情形5） h（u1），h（u2），h（u3），h（u4）互不相同.

不妨設(shè)h（u1）=1， h（u2）=2， h（u3）=3， h（u4）=4. 此時(shí)， 對(duì)每個(gè)s，t∈{5，6，…，k-1}， x，y，z，w∈{1，2，3，4}， {x，y，z，w，w}，{x，y，z，s，s}，{x，y，y，z，z}，{x，y，y，s，s}，

{x，s，s，t，t}，{x，y，z，z，z}，{x，y，s，s，s}，{x，y，y，y，y}，{x，s，s，s，s}，{s，x，x，x，x}均不是Y中頂點(diǎn)的色集合， 故不能成為Y中頂點(diǎn)色集合的5-子集的個(gè)數(shù)為

444+" 43k-51+343

+242k-51+41k-52

+343+42k-51+242

+" 41k-51+41k-51

=4k-42+26k-51+40.

能成為Y中頂點(diǎn)色集合的5-子集的個(gè)數(shù)為

k-15+" 4k-14+3k-13+3k-13

+2k-12-4k-42+26k-51+40

=" k+25+k+14+k-13-4k-42-26k+90.

因此

k+25+" k+14+k-13-4k-42

-26k+90-" k+25+k+14+k-23

-3k-22-5k+13=-13k+49.

當(dāng)k≥5時(shí)， -13k+49lt;0， 從而

k+25+" k+14+k-13-4k-42-26k+90lt;

k+25+k+14+k-23-3k-22-5k+13lt;n.

故所有這樣的5-子集不能區(qū)分Y中的n個(gè)頂點(diǎn)， 矛盾.

下證K4，n存在可用顏色有k種的點(diǎn)被多重集可區(qū)別的E-全染色. 不妨給X中的頂點(diǎn)u1，u2，u3，u4分別染顏色1，1，2，2，

則Y中的每個(gè)頂點(diǎn)在f下的色集合是{1，2，…，k}的5-子集， 且至少有一種顏色在該5-子集中只出現(xiàn)一次， 這樣的5-子集個(gè)數(shù)為

k+35+k+24+k-13-3

k-12-5k+8.

將這樣的5-子集排成一個(gè)序列， 固定該序列的第1，2，3，4，5個(gè)5-子集分別為{3，4，2，1，4}，{4，2，3，1，1}，{3，2，2，1，4}，{4，2，3，3，1}，{3，2，2，4，4}， 令Y中的頂點(diǎn)v1，v

2，…，vn依次對(duì)應(yīng)該序列中的第1，2，…，n個(gè)5-子集， 當(dāng)j=6，7…，n時(shí)， 染色方案如下：

當(dāng)vj對(duì)應(yīng)的5-子集形如{s，t，r，p，q}， s，t，r，p，q∈{3，4，…，k}且s，t，r，p，q互異時(shí)， 用顏色s，t，r，p，q分別染點(diǎn)vj和邊u1vj，u2vj，u3vj，u4vj

； 當(dāng)vj對(duì)應(yīng)的5-子集形如{s，1，2，t，r}， s，t，r∈{3，4，…，k}且s，t，r互異時(shí)， 用顏色s，1，2，t，r分別染點(diǎn)vj和邊u4vj，u1vj，u2vj，u3vj； 當(dāng)vj對(duì)應(yīng)的5-子集形如{s，t，r，p，1}， s，t，r，p∈

{3，4，…，k}且s，t，r，p互異時(shí)， 用顏色s，t，r，p，1分別染點(diǎn)vj和邊u1vj，u2vj，u3vj，u4vj； 當(dāng)vj對(duì)應(yīng)的5-子集形如{s，t，r，p，2}， s，t，r，p∈

{3，4，…，k}且s，t，r，p互異時(shí)， 用顏色s，t，r，p，2分別染點(diǎn)vj和邊u2vj，u3vj，u4vj，u1vj； 當(dāng)vj對(duì)應(yīng)的5-子集形如{s，t，r，p，p}， s，t，r，p∈

{3，4，…，k}且s，t，r，p互異時(shí)， 用顏色s，t，r，p，p分別染點(diǎn)vj和邊u1vj，u3vj，u2vj，u4vj； 當(dāng)vj對(duì)應(yīng)的5-子集形如{s，t，r，1，1}， s，t，r∈

{3，4，…，k}且s，t，r互異時(shí)， 用顏色s，t，r，1，1分別染點(diǎn)vj和邊u1vj，u2vj，u3vj，u4vj； 當(dāng)vj對(duì)應(yīng)的5-子集形如{s，t，r，2，2}， s，t，r∈

{3，4，…，k}且s，t，r互異時(shí)， 用顏色s，t，r，2，2分別染點(diǎn)vj和邊u3vj，u4vj，u1vj，u2vj； 當(dāng)vj對(duì)應(yīng)的5-子集形如{s，t，1，r，r}， s，t，r∈

{3，4，…，k}且s，t，r互異時(shí)， 用顏色s，t，1，r，r分別染點(diǎn)vj和邊u1vj，u4vj，u3vj，u2vj； 當(dāng)vj對(duì)應(yīng)的5-子集形如{s，t，2，r，r}， s，t，r∈

{3，4，…，k}且s，t，r互異時(shí)， 用顏色s，t，2，r，r分別染點(diǎn)vj和邊u3vj，u1vj，u2vj，u4vj； 當(dāng)vj對(duì)應(yīng)的5-子集形如{s，t，1，2，2}， s，t∈

{3，4，…，k}且s，t互異時(shí)， 用顏色s，t，1，2，2分別染點(diǎn)vj和邊u3vj，u4vj，u1vj，u2vj； 當(dāng)vj對(duì)應(yīng)的5-子集形如{s，t，2，1，1}， s，t∈

{3，4，…，k}且s，t互異時(shí)， 用顏色s，t，2，1，1分別染點(diǎn)vj和邊u2vj，u1vj，u3vj，u4vj； 當(dāng)vj對(duì)應(yīng)的5-子集形如{s，1，2，t，t}， s，t∈

{3，4，…，k}且s，t互異時(shí)， 用顏色s，1，2，t，t分別染點(diǎn)vj和邊u4vj，u1vj，u3vj，u2vj； 當(dāng)vj對(duì)應(yīng)的5-子集形如{s，t，t，r，r}， s，t，r∈

{3，4，…，k}且s，t，r互異時(shí)， 用顏色s，t，t，r，r分別染點(diǎn)vj和邊u1vj，u2vj，u3vj，u4vj； 當(dāng)vj對(duì)應(yīng)的5-子集形如{s，t，t，1，1}， s，t∈

{3，4，…，k}且s，t互異時(shí)， 用顏色s，t，t，1，1分別染點(diǎn)vj和邊u1vj，u2vj，u3vj，u4vj； 當(dāng)vj對(duì)應(yīng)的5-子集形如{s，t，t，2，2}， s，t∈

{3，4，…，k}且s，t互異時(shí)， 用顏色s，t，t，2，2分別染點(diǎn)vj和邊u3vj，u4vj，u1vj，u2vj； 當(dāng)vj對(duì)應(yīng)的5-子集形如{s，1，1，2，2}， s∈{

3，4，…，k}時(shí)， 用顏色s，1，1，2，2分別染點(diǎn)vj和邊u4vj，u3vj，u2vj，u1vj； 當(dāng)vj對(duì)應(yīng)的5-子集形如{s，t，r，r，r}， s，t，r∈

{3，4，…，k}且s，t，r互異時(shí)， 用顏色s，t，r，r，r分別染點(diǎn)vj和邊u1vj，u2vj，u3vj，u4vj； 當(dāng)vj對(duì)應(yīng)的5-子集形如{s，1，t，t，t}， s，t∈

{3，4，…，k}且s，t互異時(shí)， 用顏色s，1，t，t，t分別染點(diǎn)vj和邊u4vj，u1vj，u2vj，u3vj； 當(dāng)vj對(duì)應(yīng)的5-子集形如{s，2，t，t，t}， s，t∈

{3，4，…，k}且s，t互異時(shí)， 用顏色s，2，t，t，t分別染點(diǎn)vj和邊u1vj，u2vj，u3vj，u4vj； 當(dāng)vj對(duì)應(yīng)的5-子集形如{s，t，t，t，t}， s，t∈

{3，4，…，k}且s，t互異時(shí)， 用顏色s，t，t，t，t分別染點(diǎn)vj和邊u1vj，u2vj，u3vj，u4vj.

此時(shí)， Y中每個(gè)點(diǎn)的色集合剛好是事先對(duì)應(yīng)于該點(diǎn)的色集合， Y中不同頂點(diǎn)對(duì)應(yīng)的色集合不同， 所以Y中任意n個(gè)點(diǎn)彼此可區(qū)別. 當(dāng)n≥5時(shí)， X中點(diǎn)的色集合與Y中點(diǎn)的色集合的元素個(gè)數(shù)不同， 因此X中每個(gè)點(diǎn)與Y中每個(gè)點(diǎn)可區(qū)別.

下面證明（u1），（u2），（u3），（u4）互不相等. 由染色方案可知， （u3）和（u4）中都只含有一個(gè)元素

2（因?yàn)閄中頂點(diǎn)u3和u4染顏色2， 所以這兩個(gè)點(diǎn)所關(guān)聯(lián)的邊的顏色不能是2）. 當(dāng)k≥5時(shí)， （u1）和（u2）中所含元素2的個(gè)數(shù)大

于1， 故（u1）≠（u3）， （u1）≠（u4）， （u2）≠（u3）， （u2）≠（u4）.

令（ui）={f（ui），f（uiv1），…，f（uivn）}， i=1，2，3，4. 若（u1）=（u2）， 只需交換顏色f（u1v1）和f（u2v1）， 此時(shí)Y中頂點(diǎn)v1及其他頂點(diǎn)vj對(duì)應(yīng)的色集合都不變，

且（u1）中多了一種顏色f（u2v1）， 少了一種顏色f（u1v1）， 同時(shí)（u2）中多了一種顏色f（u1v1）， 少了一種顏色f（u2v1）， 即可得（u1）≠（u2）.

若（u3）=（u4）， 只需交換顏色f（u3v1）和f（u4v1）， 此時(shí)Y中頂點(diǎn)v1及其他頂點(diǎn)vj對(duì)應(yīng)的色集合都不變， 且（u3）中多了一種顏色f（u4v1）， 少了一種顏色f（u3v

1）， 同時(shí)（u4）中多了一種顏色f（u3v1）， 少了一種顏色f（u4v1）， 即可得（u3）≠（u4）. 于是可知（u1），（u2），（u3），（u4）互不相等.

證畢.

參考文獻(xiàn)

［1］" ZHANG Z F， QIU P X， LI J W， et al. Vertex-Distinguishing Total Coloring of Graphs ［J］. Ars Combinatoria， 2008， 87： 33-45.

［2］" CHEN X E， ZU Y， ZHANG Z F. Vertex-Distinguishing E-Total Colorings of Graphs ［J］. Arab J Sci Eng， 2011， 36： 1485-1500.

［3］" 李世玲， 陳祥恩， 王治文. 完全二部圖K3，n（3≤n≤17）的點(diǎn)可區(qū)別E-全染色 ［J］. 吉林大學(xué)學(xué)報(bào)（理學(xué)版）， 2015， 53（6）： 1171-

1176. （LI S L， CHEN X E， WANG Z W. Vertex-Distinguishing E-Total

Coloring of Complete Bipartite Graph K3，n with 3≤n≤17 ［J］. Journal of Jilin University （Science Edition）， 2015， 53（6）： 1171-1176.）

［4］" 李世玲， 陳祥恩， 王治文. 完全二部圖K3，n（n≥18）的點(diǎn)可區(qū)別E-全染色 ［J］. 山東大學(xué)學(xué)報(bào)（理學(xué)版）， 2016， 51（4）： 68-71.

（LI S L， CHEN X E， WANG Z W. Vertex-Distinguishing E-To

tal Coloring of Complete Bipartite Graph K3，n with n≥18 ［J］. Journal of Shandong University （Natural Science）， 2016， 51（4）： 68-71.）

［5］" 師志鳳， 陳祥恩， 王治文. 完全二部圖K6，n（6≤n≤38）的點(diǎn)可區(qū)別E-全染色 ［J］. 吉林大學(xué)學(xué)報(bào)（理學(xué)版）， 2018， 56（4）： 845-852

. （SHI Z F， CHEN X E， WANG Z W. Vertex-Distinguishing E-Tot

al Coloring of Complete Bipartite Graph K6，n with 6≤n≤38 ［J］. Journal of Jilin University （Science Edition）， 2018， 56（4）： 845-852.）

［6］" 包麗婭， 陳祥恩， 王治文. 完全二部圖K10，n（10≤n≤90）的點(diǎn)可區(qū)別E-全染色 ［J］. 山東大學(xué)學(xué)報(bào)（理學(xué)版）， 2018， 53（12）： 23-3

0. （BAO L Y， CHEN X E， WANG Z W. Vertex-Distinguishing E-To

tal Coloring of Complete Bipartite Graph K10，n with 10≤n≤90 ［J］. Journal of Shandong University （Natural Science）， 2018， 53（12）： 23-30.）

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

（CHEN X E. A Survey on Not Necessarily Proper Colorings under Which C

ertain Pairs of Vertices Are Distinguished by Nonmultiple Color Sets ［J］. Journal of Guangzhou University （Natural Science Edition）， 2019， 18（4）： 50-59.）

［8］" 陳祥恩， 曹靜. 圈與路的點(diǎn)被多重集可區(qū)別的E-全染色 ［J］. 華東師范大學(xué)學(xué)報(bào)（自然科學(xué)版），

2024， 2024（2）： 14-22. （CHEN X E， CAO J. E-Total Coloring of Cycles and Paths Which Ar

e Vertex-Distinguished by Multiple Sets ［J］. Journal of East China Normal University （Natural Science）， 2024， 2024（2）： 14-22.）

［9］" 曹靜， 陳祥恩. 輪與扇的點(diǎn)被多重集可區(qū)別的E-全染色 ［J］. 山東大學(xué)學(xué)報(bào)（理學(xué)版）， 2024， 59（2）： 38-46. （CAO J， CHEN X E. E-Total Co

loring of Wheels and Fans" Vertex＼|Distinguished by Multiple Sets ［J］. Journal of Shandong University （Natural Science）， 2024， 59（2）： 38-46.）

［10］" 邵嘉裕. 組合數(shù)學(xué) ［M］. 上海： 同濟(jì)大學(xué)出版社， 1990：

5-14. （SHAO J Y. Combinatorial Mathematics ［M］. Shanghai： Tongji University Press， 1990： 5-14.）

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