K5;5; p 的点可区别的 IE-全染色(p ?2 028)

闫瑞敏 陈祥恩

摘要： 图 G 的 IE-全染色 f 是指对?u; v ∈ V（G） ， 使得 f （u）  f （v）的一个一般全染色 ， 其中 u; v 相邻 ， V（G）是图 G 的顶点集.设 f 是图 G 的 IE-全染色 ， 图 G 的一个顶点 x 在 f 下的色集合C（x）是指由x 及 x 的关联边的颜色所构成的集合（非多重集）.若图 G 的任意两个不同顶点的色集合不同 ， 则 f 称为图 G 的点可区别的 IE-全染色（简记为VDIETC）.利用色集合事先分配法、构造染色法及反证法探讨了完全三部图 K5;5;p （p ?2 028）的点可区别的 IE-全染色问题 ， 确定了 K5;5;p   （p ?2 028）的点可区别的 IE-全色数.

关键词：完全三部图;  IE-全染色;  点可区别的 IE-全染色;  点可区别的 IE-全色数

中图分类号： O157.5    文献标志码： A    DOI： 10.3969/j.issn.1000-5641.2022.02.003

Vertex-distinguishing IE-total coloring of K5; 5; p   （p ?2 028）

YAN Ruimin，  CHEN Xiangen

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

Abstract： Let G  be a simple graph. A total coloring f  of G  is called an IE-total coloring if f （u）  f （v） for any two adjacent vertices u  and v ， where V（G） denotes the set of vertices of G . For an IE-total coloring f  of G ， the set of colors C（x） （non-multiple sets） of vertex x  under f  of G  is the set of colors of vertex x  and of the edges incident with x . If any two distinct vertices of G  have distinct color sets， then f  is called a vertex-distinguishing IE-total coloring of G . We explore the vertex distinguishing IE-total coloringof complete tripartite graphs K5;5;p （p ?2 028） through the use of multiple methods， including distributing the color sets in advance， constructing the colorings， and contradiction. The vertex-distinguishing IE-total chromatic number of K5;5;p （p ?2 028） is determined.

Keywords： complete tripartite graph;   IE-total coloring;   vertex-distinguishing IE-total coloring;   vertex- distinguishing IE-total chromatic number

0  引言

點可区别一般边染色在文献[1-6]中均有研究 .近年来 ， 点可区别的未必正常的全染色也被研究. 在文献[7]中提出了点可区别的 IE-全染色. 文献[8]对点可区别一般全染色进行了讨论 ， 文献 [9-11]对图的优美性、线性代数理论以及图和星的合成的点可区别正常边染色给出了相关结果.文献[12]研究了完全三部图 K2;n;p   （2? n ?5）的点可区别的 IE-全染色和一般全染色 ， 并确定了它们的点可区别的 IE-全色数和一般全色数.

图G 的 IE-全染色f 是指对图G 的任意2个相邻顶点u; v ， 使得f （u）  f （v）的一个一般全染色;图G 的 k-IE-全染色是指使用了k 种颜色的图G 的 IE-全染色;图G 的 k-点可区别的 IE-全染色是指使用了 k 种颜色的点可区别的 IE-全染色（简记为k-VDIETC）.点可区别是指图G 中任意2个不同的顶点的色集合不同. 图G 的 IE-全色数是指对图G 进行 IE-全染色所需要的最少颜色数;图G的点可区别的 IE-全色数是指对图G进行点可区别的 IE-全染色所需要的最少颜色数 ， 记为vt（ie）（G）.

本文研究 K5;5;p 的点可区别的 IE-全染色 ， 并给出了它们的点可区别 IE-全色数. 文中述及的完全三部图 Km;n;p 的顶点集合为 V = X ∪ Y ∪ Z ， 其中 X ={x1; x2; ·· ·; xm}; Y ={y1; y2; ·· ·; yn}; Z ={z1; z2; ·· ·; zp} ， 边集合为{xiyj |i =1;2;· ·· ; m; j =1;2;· ·· ; n}∪ {yjzt|j =1;2;· ·· ; n; t =1;2;· ·· ; p}∪{xizt |i =1;2;· ·· ; m; t =1;2;· ·· ; p}.FCD86179-7F39-4C2E-AD6D-ACE81DE4BD3A

本文约定：当考虑图 G 的 l-VDIETC 时 ， 用 C（x）表示点 x 的色集合在全体颜色构成的集合 {1;2;· ·· ; l}中的补集 ， 即 C（x）= {1;2;· ·· ; l}＼C（x）. {1;2;· ·· ; l}的含有i 个元素的子集叫i -子集.

1  准备工作

引理1当 k ?14且p >  （k i 1）? 10时 ， K5;5;p 不存在（k ?1）-VDIETC.

证明用反证法. 假设 K5;5;p 存在（k?1）-VDIETC， 设为 g.

断言1  ?a ∈{1;2;· ·· ; k ?1} ， {a}不是 X ∪ Y 中任一点的色集合.

否则 ， 不妨设a =1 且C（x1）= {1} ， 则 Z 中每个点的色集合必含1， 故p ? ∑（k i2） ， 与p >∑ （k i 1）?10矛盾.

断言2  任意2 -子集均不是 X ∪ Y 中任一点的色集合.

否则 ， 不妨设C（x1）= {1;2}且g（x1）= 1. 此时 Z 中每个点的色集合必含1 或2.在{1;2;· ·· ; k ?1}中， 含1 不含2 且最多含有11个元素的子集的个数为 （k i3）;含 2不含1 且最多含有11个元素的子集的个数为∑ （k i3）;同时含1 和2 且最多含有11个元素的子集的个数为∑ （k i3） ， 故p ? ∑（k i3）+∑（k i3）+∑ （k i3） ， 这与p >∑ （k i 1）? 10矛盾.

断言3  任意3-子集均不是 X ∪ Y 中任一点的色集合.

否则 ， 不妨设 C（x1）= {1;2;3}且 g（x1）= 1. 此时 Z 中每個点的色集合必含1， 2或 3.在 {1;2;· ·· ;k ?1}中 ， 含1 不含2 和3 且最多含有11个元素的子集的个数为 （k i4）;含 2不含1 和3 且最多含有11个元素的子集的个数为∑ （k i4）;含 3不含1 和2 且最多含有11个元素的子集的个数为∑ （k i4）;含1 和2但不含3 且最多含有11个元素的子集的个数为 （k i4）;含 1和 3但不含2 且最多含有11个元素的子集的个数为∑ （k i4）;含 2和 3但不含1 且最多含有11个元素的子集的个数为∑ （k i4）;同时含1，2，3， 且最多含有11个元素的子集的个数为 ， 故，矛盾.

（1）当 {g（xi）|i =1;2;3;4;5}∪ {g（yj）|j =1;2;3;4;5}里互不相同的颜色至少有 3种时 ， 不妨设 {1;2;3}? {g（xi）|i =1;2;3;4;5}∪ {g（yj）|j =1;2;3;4;5} ， 那么{1}; {2}; {3}; {1;2}; {1;3};{2;3};{1;2;3}均不能作为 Z 中任一点的色集合 ， 由断言1—3可知 ， {1};{2};{3};{1;2};{1;3};{2;3};{1;2;3}也均不是 X ∪ Y 中任一点的色集合 ，  C（xi）  {1;2;3} ，  C（yj）  {1;2;3} ， i; j =1;2;3;4;5 ， 且 C（xi）和 C（yj）（i; j =1;2;3;4;5）中最多有6 个集合属于{{1}; {2}; {3}; {1;2}; {1;3}; {2;3}}. 因此 ， 这10个集合中至少还有4 个集合均不属于{{1};{2};{3};{1;2};{1;3};{2;3};{1;2;3}} ， 不妨设为 C（x1） ， C（y1） ， C（y2） ，C（y3） ， 其中至少有1 个是? ， 不妨设 C（x1）= ? ， C（yj）  ?; j =1;2;3 .

当 |C（y1）|? 11 ， |C（y2）|? 11 ， |C（y3）|? 11时 ， {1};{2};{3};{1;2};{1;3};{2;3};{1;2;3} ，  C（y1） ，C（y2） ， C（y3）均不是 Z 中任一点的色集合 ， 故p ? ∑（k i 1）? 10 ， 与p >∑ （k i 1）? 10矛盾.

当 |C（y1）|? 11 ， |C（y2）|? 11 ， |C（y3）|? 12时 ， {1};{2};{3};{1;2};{1;3};{2;3};{1;2;3} ，  C（y1） ，C（y2）及  C（y3）的 1-子集 ， 2 -子集 ， · ·· ;  11-子集均不是 Z 中任一点的色集合 ， 故p ? ∑（k i 1）? 9? ∑（1i2）= ∑（k i 1）? 4103 ， 与p >∑ （k i 1）? 10矛盾.

当|C（y1）|? 11 ， |C（y2）|? 12 ， |C（y3）|? 12时 ， {1};{2};{3};{1;2};{1;3};{2;3};{1;2;3} ，  C（y1）及 C（yj） ，  j =2;3 ， 的 1-子集 ， 2 -子集 ， · ·· ;  11-子集均不是 Z 中任一点的色集合 ， 故p ? ∑（k i 1）? 8? 2∑ （1i2）= ∑（k i 1）? 8196 ， 与p >∑ （k i 1）? 10矛盾.

当|C（y1）|? 12 ， |C（y2）|? 12 ， |C（y3）|? 12时 ， C（yj） （j =1;2;3 ）的 1-子集 ， 2-子集 ， ·· ·; 11-子集均不是 Z 中任一点的色集合 ， 故p ? ∑（k i 1）? 3∑ （1i2）= ∑（k i 1）? 12282 ， 与p >∑ （k i 1）? 10矛盾.FCD86179-7F39-4C2E-AD6D-ACE81DE4BD3A

（2）当 {g（xi）|i =1;2;3;4;5}∪ {g（yj）|j =1;2;3;4;5}里互不相同的颜色仅有2 种时 ， 设 g（xi）= 1; g（yj）= 2（i; j =1;2;3;4;5）.

断言4  在（2）下， {1};{2};{1;2}均不能作为 Z 中任一点的色集合.

断言5  在（2）下， {3};{4};{5};· ·· ;{k ?1}中至少有2 个集合不是 Z 中任一点的色集合.

否则 ， 至多有1 个集合不是 Z 中任一点的色集合， 不妨设{4};{5};· ·· ;{k ?1}均是 Z 中任一点的色集合 ， 则 C（xi）∩ C（yj）? {4;5;· ·· ; k ?1}; i; j =1;2;3;4;5 ， 此时 C（xi）; C（yj）; i; j =1;2;3;4;5 ， 这10个集合只能被分配{1;4;5;· ·· ; k ?1};{2;4;5;· ·· ; k ?1};{1;2;4;5;· ·· ; k ?1};{1;3;4;5;· ·· ; k ?1};{2;3;4;5;· ·· ; k ?1};{1;2;3;4;5;· ·· ; k ?1}这 6个集合 ， 不能区分xi; yj（i; j =1;2;3;4;5）这 10个顶点 ， 矛盾.

由断言5， 不妨设{3};{4}不是 Z 中任一点的色集合 ， 由断言1、2、4可知 ， {1};{2};{3};{4};{1;2}均不是任一点的色集合.下面考虑 C（xi） ， C（yj） ， i; j =1;2;3;4;5 ， 这10个集合互不相同 ， 且其中至少有 5个集合不属于{?;{1};{2};{3};{4}} ， 不妨设 C（x1） ， C（y1） ， C（y2） ， C（y3） ， C（y4）都不属于{?;{1};{2};{3};{4}}. C（x1）不含1， 且不是 X 中任一點的色集合 ， C（yj）; j =1;2;3;4 ， 不含2， 且不是 Y 中任一点的色集合 .由于相邻2 点的色集合之交非空 ， 故 C（x1）不是 Y ∪ Z 中任一点的色集合 ，  C（yj）; j =1;2;3;4 ， 不是 X ∪ Z 中任一点的色集合 ， 则 C（x1） ， C（y1） ， C（y2） ， C（y3） ， C（y4）均不是任一点的色集合. 因此{1};{2};{3};{4};{1;2} ， C（x1） ， C（y1） ， C（y2） ， C（y3） ， C（y4）这 10个集合互不相同 ， 且均不是任一点的色集合， 故p ?  （k i 1）? 10 ， 矛盾.

引理2  当k ?14且 ∑（k i 1）? 10< p ? ∑（i（k））? 10时 ， K5;5;p 存在 k -VDIETC.

证明为了给出 K5;5;p 的 k-IE-全染色 ， 先对 K5;5;p 的每个顶点对应 {1;2;· ·· ; k}的一个子集 ，令 D（x1）= {1;2;· ·· ; k}; D（x2）=D（x1）＼ {2}; D（x3）=D（x1）＼ {3}; D（x4）= D（x1）＼ {4}; D（x5）=D（x1）＼{5}; D（y1）=D（x1）＼{1}; D（y2）=D（x1）＼{6} ， D（y3）= D（x1）＼ {7} ， D（y4）=D（x1）＼ {8} ， D（y5）= D（x1）＼{9} ， D（zi）= {i +9} ， i=1;2;· ·· ; k ?9 ， D（zk  8）= {1;10} ， D（zk  7）= {2;10} ， D（zk  6）= {3;10} ， D（zk  5）= {4;10} ， D（zk  4）= {5;10} ， D（zk  3）= {6;10} ， D（zk  2）= {7;10} ， D（zk  1）= {8;10} ， D（zk）= {9;10}.

将除{1;2};{1;10}; {2;10}; {3;10}; {4;10}; {5;10}; {6;10}; {7;10}; {8;10}; {9;10}外的{1;2;· ·· ;k}的 2-子集 ， 3-子集 ， ·· ·; 11-子集排成一个序列 1. 令 D（zk+1） ， D（zk+2） ， ·· ·;  D（zp）依次是 1中的第1;2;· ·· ; p ? k 项. 这一点是可以做到的 ， 因为1中含有（）+（）+· ·· +（） ?10项 ， 而p ? k ?（ ）+（）+· ·· +（） ?10 ， 即p ?  （i（k））? 10.

下面给出 K5;5;p 的k -IE-全染色 g .令g（xi）= 1; g（yj）= 2（i; j =1;2;3;4;5）. 用max{D（zi）}染点 zi ，i =1;2;· ·· ; p .

当|D（zi）|= 2时 ， g（uzi）= min{D（u）∩ D（zi）} ， u ∈ X ∪ Y ， i =1;2;· ·· ; p .

当|D（zi）|= 3时 ， g（uzi）= min{D（u）∩ D（zi）} ， u ∈{x2; x3; x4; x5; yj} ， g（x1zi）= min{D（x1）∩D（zi）＼{g（x2zi）; g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， i =1;2;· ·· ; p ， j =1;2;3;4;5 .

当|D（zi）|= 4时 ， g（uzi）= min{D（u）∩ D（zi）} ， u ∈{x3; x4; x5; yj} ， g（x2zi）= min{D（x2）∩ D（zi）＼{g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x1zi）  =g（yjzi）}} ， i =1;2;· ·· ; p ， j =1;2;3;4;5 .FCD86179-7F39-4C2E-AD6D-ACE81DE4BD3A

当|D（zi）|=5时 ， g（uzi）= min{D（u）∩ D（zi）} ，min{D（x1）∩D（zi）＼{g（x2zi）; g（x3zi）; g（x4zi）; g（x5zi）;u ∈{x4; x5; yj} ， g（x3zi）= min{D（x3）∩ D（zi）＼ {g（x4zi）;g（x5zi）; g（yjzi）}} ， g（x2zi）= j（i）n{D（x2）∩ D（zi）＼{g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x1zi）= j（i）n{D（x1）∩ D（zi）＼ {g（x2zi）; g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， i =1;2;· ·· ; p ， j =1;2;3;4;5 .

当|D（zi）|=6 时 ， g（uzi）=  min{D（u）∩ D（zi）} ，g（yjzi）}} ， g（x3zi） = j（i）n{D（x3）∩ D（zi）＼ {g（x4zi）;u ∈{x5; yj} ， g（x4zi）= min{D（x4）∩ D（zi）＼ {g（x5zi）;g（x5zi）; g（yjzi）}} ， g（x2zi） = min{D （x2）∩ D（zi）＼{g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x1zi）= j（i）n{D（x1）∩ D（zi）＼ {g（x2zi）; g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， i =1;2;· ·· ; p ， j =1;2;3;4;5 .

当|D（zi）|=7 时 ， g（uzi）=  min{D（u）∩ D（zi）} ， u ∈{y1; y2; y3; y4; y5} ， g（x5zi）= min{D（x5）∩ D（zi）＼{g（yjzi）}} ， g（x4zi）= j（i）n{D（x4）∩D（zi）＼{g（x5zi）; g（yjzi）}} ， g（x3zi）= j（i）n{D（x3）∩D（zi）＼{g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x2zi）=  j（i）n{D（x2）∩ D（zi）＼{g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x1zi）=  j（i）n{D（x1）∩D（zi）＼{g（x2zi）; g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， i =1;2;· ·· ; p ， j =1;2;3;4;5 .

当|D（zi）|=8时 ， g（uzi）=min{D（u）∩D（zi）} ， u ∈{y2; y3; y4; y5} ， g（y1zi）=min{D（y1）∩ D（zi）＼{g（y2zi）;g（y3zi）; g（y4zi）; g（y5zi）}} ， g（x5zi）= j（i）n{D（x5）∩D（zi）＼{g（yjzi）}} ， g（x4zi）= j（i）n{D（x4）∩D（zi）＼{g（x5zi）; g（yjzi）}} ， g（x3zi）= j（i）n{D（x3）∩D（zi）＼{g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x2zi）= j（i）n{D（x2）∩D（zi）＼{g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x1zi）=  j（i）n{D（x1）∩D（zi）＼{g（x2zi）; g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， i =1;2;· ·· ; p ， j =1;2;3;4;5 .

當|D（zi）|=9时 ， g（uzi）=min{D（u）∩ D（zi）} ， u ∈{y3; y4; y5} ， g（y2zi）= min{D（y2）∩ D（zi）＼ {g（y3zi）;g（y4zi）; g（y5zi）}} ， D（zi）＼{g（yjzi）}} ， g（x5zi）; g（yjzi）}} ，g（y1zi）= min{D（y1）∩D（zi）＼{g（y2zi）; g（y3zi）; g（y4zi）; g（y5zi）}} ， g（x5zi）= min{D（x5）∩g（x4zi）= min{D（x4）∩D（zi）＼{g（x5zi）; g（yjzi）}} ， g（x3zi）=min{D（x3）∩D（zi）＼{g（x4zi）;g（x2zi）= min{D（x2）∩D（zi）＼{g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x1zi）= min{D（x1）∩D（zi）＼ {g（x2zi）; g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， i =1;2;· ·· ; p ， j =1;2;3;4;5 .

当|D（zi）|=10时 ， g（uzi）= min{D（u）∩ D（zi）} ， u ∈{y4; y5} ， g（y3zi）= min{D（y3）∩ D（zi）＼ {g（y4zi）;g（y5zi）}} ， g（y2zi）=        i（mi）n{D（y2）∩D（zi）＼{g（y3zi）; g（y4zi）; g（y5zi）}} ， g（y1zi）=      i（mi）n{D（y1）∩D（zi）＼{g（y2zi）;g（y3zi）; g（y4zi）; g（y5zi）}} ， g（x5zi）= j（i）n{D（x5）∩D（zi）＼{g（yjzi）}} ， g（x4zi）= j（i）n{D（x4）∩D（zi）＼{g（x5zi）; g（yjzi）}} ， g（x3zi）= j（i）n{D（x3）∩D（zi）＼{g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x2zi）= j（i）n{D（x2）∩D（zi）＼{g（x3zi）;g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x1zi）= j（i）n{D（x1）∩ D（zi）＼{g（x2zi）; g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， i =1;2;· ·· ; p ， j =1;2;3;4;5 .FCD86179-7F39-4C2E-AD6D-ACE81DE4BD3A

当|D（zi）|=11时 ， g（y5zi）= min{D（y5）∩ D（zi）} ， g（y4zi）= min{D（y4）∩D（zi）＼ {g（y5zi）}} ， g（y3zi）=min{D（y3）∩D（zi）＼{g（y4zi）; g（y5zi）}} ， g（y2zi）= min{D（y2）∩D（zi）＼{g（y3zi）; g（y4zi）; g（y5zi）}} ， g（y1zi）=min{D（y1）∩D（zi）＼{g（y2zi）; g（y3zi）; g（y4zi）; g（y5zi）}} ， g（x5zi）= min{D（x5）∩D（zi）＼{g（yjzi）}} ， g（x4zi）=min{D（x4）∩D（zi）＼{g（x5zi）; g（yjzi）}} ， g（x3zi）= min{D（x3）∩D（zi）＼{g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x2zi）=min{D（x2）∩ D（zi）＼ {g（x3zi）; g（x4zi）; g（x5zi）; g（yjzi）}} ， g（x1zi）= min{D（x1）∩ D（zi）＼ {g（x2zi）; g（x3zi）;g（x4zi）; g（x5zi）; g（yjzi）}} ， i =1;2;· ·· ; p ， j =1;2;3;4;5 .

用min{D（x）∩ D（y）}染邊xy ， ?x ∈ X;?y ∈ Y .

最后得到 K5;5;p 的k -IE-全染色g 是点可区别的 ， 因为?v ∈ V（K5;5;p） ， K5;5;p 均有C（v）= D（v）.

2  主要结果及其证明

定理1

证明分以下几种情况进行讨论.

情形1  当k ?14且 ∑（k i 1）? 10< p ? ∑（i（k））? 10时vt（ie）（K5;5;p）= k .

由引理1、引理2 可得结论成立.

情形2  当4 076? p ?8 167时vt（ie）（K5;5;p）= 13.

第1 步 ， 用反证法证明 K5;5;p 不存在12-VDIETC;第 2步具体构造出13-VDIETC.假设 K5;5;p 存在 12-VDIETC.

断言1  ?a ∈{1;2;· ·· ;12} ， {a}不是 X ∪ Y 中任一点的色集合.

否则 ， 不妨设a =1 且C（x1）= {1} ， 则 Z 中每个点的色集合必含1， 故p ?， 矛盾.

断言2任意2 -子集均不是 X ∪ Y 中任一点的色集合.

否则 ， 不妨设 C（x1）= {1;2}且 g（x1）= 1. 此时 Z 中每个点的色集合必含1 或2.在 {1;2;· ·· ;12}中 ， 含1 不含2 且最多含有11个元素的子集的个数为 （1i0）;含 2不含1 且最多含有11个元素的子集的个数为∑ （1i0）;同时含1 和2 且最多含有11个元素的子集的个数为∑ （1i0） ， 故p ?2 ∑（1i0）+ （1i0）+ 1= 3069 ， 矛盾.

断言3  任意3 -子集均不是 X ∪ Y 中任一点的色集合.

否则 ， 不妨设 C（x1）= {1;2;3}且 g（x1）= 1. 此时 Z 中每个点的色集合必含1，2或 3.在{1;2;· ·· ;12}中 ， 含1 不含2，3且最多含有11个元素的子集的个数为 （）;含 2不含1，3且最多含有11个元素的子集的个数为∑ （）;含 3不含1，2且最多含有11个元素的子集的个数为∑ （）;含 1，2不含3 且最多含有11个元素的子集的个数为∑ （）;含 1，3不含2 且最多含有11个元素的子集的个数为∑ （）;含2，3不含1 且最多含有11个元素的子集的个数为 （）;同时含1，2，3且最多含有11个元素的子集的个数为∑ （） ， 故p ? ∑（ ）+ 5∑ （） +∑ （） =3 581 ， 矛盾.

（1）当{g（xi）|i =1;2;3;4;5}∪ {g（yj）|j =1;2;3;4;5}里互不相同的颜色至少有3 种时 ， 不妨设{1;2;3}? {g（xi）|i =1;2;3;4;5}∪ {g（yj）|j =1;2;3;4;5}. 那么 {1};{2};{3};{1;2};{1;3};{2;3};{1;2;3}均不能作为 Z 中任一点的色集合 ， 由断言1—3可知 ， {1};{2};{3};{1;2};{1;3};{2;3};{1;2;3}也均不是 X ∪ Y 中任一点的色集合， C（xi）{1;2;3} ， C（yj）{1;2;3} ， i; j =1;2;3;4;5 ， 且其中至少有3 个集合不属于{{1};{2};{3};{1;2};{1;3};{2;3};?} ， 不妨设为 C（x1） ， C（y1） ， C（y2）.

1） C（x1）不是X 中任一点的色集合且 C（y1） ， C（y2）不是 Y 中任一点的色集合， 则10+p ?  （1i2）?10 ， 即p ?4 075 ， 矛盾.

2） C（x1）是 X 中点的色集合且 C（y1） ， C（y2）不是 Y 中任一点的色集合 ， 则{4};{5};· ·· ;{12}均不是任一点的色集合， 故10+p ?  （1i2）? 18 ， 即p ?4 067 ， 矛盾.

3） C（x1）是 X 中点的色集合且 C（y1） ， C（y2）中有1 个是 Y 中点的色集合 ， 则{4};{5};· ·· ;{12}均不是任一点的色集合， 故10+p ?  （1i2）? 17 ， 即p ?4 068 ， 矛盾.

4） C（x1） ， C（y1） ， C（y2）都是 X ∪ Y 中点的色集合 ， 则{4};{5};· ·· ;{12}均不是任一点的色集合 ，故10+p ?  （1i2）? 16 ， 即p ?4 069 ， 矛盾.FCD86179-7F39-4C2E-AD6D-ACE81DE4BD3A

（2）当 {g（xi）|i =1;2;3;4;5}∪ {g（yj）|j =1;2;3;4;5}里互不相同的颜色仅有2 种时 ， 设 g（xi）= 1; g（yj）= 2（i; j =1;2;3;4;5）.

断言4  在（2）下， {1};{2};{1;2}均不能作为 Z 中任一点的色集合.

断言5  在（2）下， {3};{4};{5};· ·· ;{12}中至少有2 个集合不是 Z 中任一点的色集合.

否则 ， 至多有1 个集合不是 Z 中任一点的色集合 ， 不妨设{4};{5};· ·· ;{12}均是 Z 中任一点的色集合 ， 则 C（xi）∩ C（yj）? {4;5;· ·· ;12}; i; j =1;2;3;4;5 ， 此时 C（xi）; C（yj）; i; j =1;2;3;4;5 ， 这10个集合只能被分配{1;4;5;· ·· ;12}; {2;4;5;· ·· ;12}; {1;2;4;5;· ·· ;12}; {1;3;4;5;· ·· ;12};{2;3;4;5;· ·· ;12};{1;2;3;4;5;· ·· ;12}这 6个集合 ， 不能区分xi; yj（i; j =1;2;3;4;5）这 10个顶点 ， 矛盾.

由断言5， 不妨设{3};{4}不是 Z 中任一点的色集合 ， 由断言1、2、4可知{1};{2};{3};{4};{1;2}均不是任一点的色集合.下面考虑 C（xi） ， C（yj） ， i; j =1;2;3;4;5 ， 这10个集合互不相同 ， 且至少有5 个不属于 {?;{1};{2};{3};{4}} ， 不妨设 C（x1） ，  C（y1） ，  C（y2） ，  C（y3） ，  C（y4）都不属于{?;{1};{2};{3};{4}}. C（x1）不含1 且不是 X 中任一点的色集合 ， C（yj）; j =1;2;3;4 ， 不含2， 不是 Y 中任一点的色集合 ， 由于相邻 2点的色集合之交非空 ， 故 C（x1）不是 Y ∪ Z 中任一点的色集合 ，  C（yj）; j =1;2;3;4 ， 不是 X ∪ Z 中任一点的色集合 ， 则 C（x1） ， C（y1） ， C（y2） ， C（y3） ， C（y4）均不是任一点的色集合 ， 因此{1};{2};{3};{4};{1;2} ， C（x1） ， C（y1） ， C（y2） ， C（y3） ， C（y4）这 10个集合互不相同 ， 且均不是任一点的色集合， 故10+p ?  （1i2）? 10 ， 即p ?4 075 ， 矛盾.

下面给出 K5;5;8167的 13-VDIETC.令 D（x1）= {1;2;· ·· ;13}; D（x2）= D（x1）＼ {2}; D（x3）= D（x1）＼{3}; D（x4）= D（x1）＼ {4}; D（x5）=D（x1）＼ {5}; D（y1）= D（x1）＼ {1}; D（y2）=D（x1）＼ {6} ， D（y3）= D（x1）＼{7} ， D（y4）= D（x1）＼ {8}; D（y5）= D（x1）＼ {9} ， 将除 {1;2};{1};{2};{3};{4};{5};{6};{7};{8};{9}外的{1;2;· ·· ;13}的其余1 -子集 ， 2-子集; ·· ·; 11-子集作为 Z 中点的色集合.据此可参照引理2 的证明过程中所述的染法给出 K5;5;8167的 13-VDIETC.当 4076?p ?8 166时 ，  K5;5;p 的13-VDIETC 可由  K5;5;8167的13-VDIETC 在 X ∪ Y ∪{z1; z2; ·· ·; zp}所导出的子图上的限制给出.

情形3  当2 028? p ?4 075时 ， vt（ie）（K5;5;p）= 12.

先用反证法证明 K5;5;p 不存在11-VDIETC.假如 K5;5;p 存在11-VDIETC.

断言1  ?a ∈{1;2;· ·· ;11} ， {a}不是 X ∪ Y 中任一点的色集合.

否则 ， 不妨设a =1 且C（x1）= {1} ， 则 Z 中每个点的色集合必含1， 故p ? （1i0）= 1023 ， 矛盾.

断言2  任意2 -子集均不是 X ∪ Y 中任一点的色集合.

否则 ， 不妨设 C（x1）= {1;2}且 g（x1）= 1. 此时 Z 中每个点的色集合必含1 或2.在 {1;2;· ·· ;11}中 ， 含1 不含2 且最多含有11个元素的子集的个数为（ ）;含 2不含1 且最多含有11个元素的子集的个数为∑ （）;同时含 1和 2且最多含有 11个元素的子集的个数为∑ （） ， 故p ?2 ∑（ ）+ （） =1 534 ， 矛盾.

断言3  任意3 -子集均不是 X ∪ Y 中任一点的色集合.

否则 ， 不妨设 C（x1）= {1;2;3}且 g（x1）= 1. 此时 Z 中每个点的色集合必含1，2或 3.在 {1;2;· ·· ;11}中 ， 含1 不含2，3且最多含有11个元素的子集的个数为 （）;含 2不含1，3且最多含有11个元素的子集的个数为∑ （）;含 3不含1，2且最多含有11个元素的子集的个数为∑ （）;含 1，2不含3 且最多含有11个元素的子集的个数为∑ （）;含 1，3不含2 且最多含有11个元素的子集的个数为∑ （）;含2，3不含1 且最多含有11个元素的子集的个数为 （）;同时含1，2，3且最多含有11个元素的子集的个数为∑ （） ， 故p ?2 ∑（ ）+ 5∑ （） =1 790 ， 矛盾.FCD86179-7F39-4C2E-AD6D-ACE81DE4BD3A

（1）当 {g（xi）|i =1;2;3;4;5}∪ {g（yj）|j =1;2;3;4;5}里互不相同的颜色至少有 3种时 ， 不妨设{1;2;3}? {g（xi）|i =1;2;3;4;5}∪ {g（yj）|j =1;2;3;4;5}. 那么 {1};{2};{3};{1;2};{1;3};{2;3};{1;2;3}均不能作为 Z 中任一点的色集合 ， 由断言1—3可知 ， {1};{2};{3};{1;2};{1;3};{2;3};{1;2;3}也均不是X ∪ Y 中任一点的色集合， C（xi）  {1;2;3} ， C（yj）  {1;2;3} ， i; j =1;2;3;4;5 ， 且至少有3 个不属于{{1};{2};{3};{1;2};{1;3};{2;3};?}. 不妨设为 C（x1） ， C（y1） ， C（y2）.

1）当  C（x1） ，  C（y1） ，  C（y2）都不是 X ∪ Y 中任一点的色集合时 ， 有10+p ?  （1i1）? 10 ， 即p ?2 027 ， 矛盾.

2）当 C（x1） ， C（y1） ， C（y2）中只有1 个是 X ∪ Y 中点的色集合时 ， 此时{4};{5};· ·· ;{11}均不是任一点的色集合， 故10+p ?  （1i1）? 17 ， 即p ?2 020 ， 矛盾.

3）当 C（x1） ， C（y1） ， C（y2）中只有2 个是 X ∪ Y 中点的色集合时 ， 此时{4};{5};· ·· ;{11}均不是任一点的色集合， 故10+p ?  （1i1）? 16 ， 即p ?2 021 ， 矛盾.

4）当 C（x1） ， C（y1） ， C（y2）都是 X ∪ Y 中点的色集合时 ， 此时{4};{5};· ·· ;{11}均不是任一点的色集合， 故10+p ?  （1i1）? 15 ， 即p ?2 022 ， 矛盾.

（2）当 {g（xi）|i =1;2;3;4;5}∪ {g（yj）|j =1;2;3;4;5}里互不相同的颜色仅有2 种时 ， 设 g（xi）= 1; g（yj）= 2（i; j =1;2;3;4;5）.

断言4  在（2）下， {1};{2};{1;2}均不能作为 Z 中任一点的色集合.

断言5  在（2）下， {3};{4};{5};· ·· ;{11}中至少有2 个集合不是 Z 中任一点的色集合.

否则 ， 至多有1 个集合不是 Z 中任一点的色集合， 不妨设{4};{5};· ·· ;{11}均是 Z 中任一点的色集合 ， 则 C（xi）∩ C（yj）? {4;5;· ·· ;11}; i; j =1;2;3;4;5 ， 此时 C（xi）; C（yj）; i; j =1;2;3;4;5 ， 这10个集合只能被分配{1;4;5;· ·· ;11}; {2;4;5;· ·· ;11}; {1;2;4;5;· ·· ;11}; {1;3;4;5;· ·· ;11};{2;3;4;5;· ·· ;11};{1;2;3;4;5;· ·· ;11}这 6个集合 ， 不能区分xi; yj（i; j =1;2;3;4;5）这 10个顶点 ， 矛盾.

由断言5， 不妨设{3};{4}不是 Z 中任一点的色集合 ， 由断言1、2、4可知{1};{2};{3};{4};{1;2}均不是任一点的色集合.下面考虑 C（xi） ， C（yj） ， i; j =1;2;3;4;5 ， 这10个集合互不相同 ， 且至少有5 个不属于{?;{1};{2};{3};{4}} ， 不妨设 C（x1） ， C（y1） ， C（y2） ， C（y3） ， C（y4）都不属于{?;{1};{2};{3};{4}}. C（x1）不含1， 不是 X 中任一点的色集合， C（yj）; j =1;2;3;4 ， 不含2， 不是 Y 中任一点的色集合.由于相邻2 点的色集合之交非空 ， 故 C（x1）不是 Y ∪ Z 中任一点的色集合 ， C（yj）; j =1;2;3;4 ， 不是 X ∪ Z 中任一点的色集合， 则 C（x1） ， C（y1） ， C（y2） ， C（y3） ， C（y4）均不是任一点的色集合， 因此{1};{2};{3};{4};{1;2} ， C（x1） ， C（y1） ， C（y2） ， C（y3） ， C（y4）这 10个集合互不相同 ， 且均不是任一点的色集合， 故10+p ?  （1i1）? 10 ， 即p ?2 027 ， 矛盾.

下面给出 K5;5;4075的 12-VDIETC.令 D（x1）= {1;2;· ·· ;12}; D（x2）= D（x1）＼ {2}; D（x3）= D（x1）＼{3}; D（x4）= D（x1）＼ {4}; D（x5）=D（x1）＼ {5}; D（y1）= D（x1）＼ {1}; D（y2）= D（x1）＼ {6} ， D（y3）=D（x1）＼{7} ， D（y4）=D（x1）＼{8}; D（y5）= D（x1）＼{9} ， 将除{1;2};{1};{2};{3};{4};{5};{6};{7};{8};{9}外的{1;2;· ·· ;12}的其余1 -子集 ， 2-子集 ， ·· ·; 11-子集作为 Z 中任一点的色集合. 据此可参照引理2 的证明过程中所述的染法给出 K5;5;4075的 12-VDIETC.当 2028?p ?4 074时 ， K5;5;p 的12-VDIETC 可由 K5;5;4075的 12-VDIETC 在 X ∪ Y ∪{z1; z2; ·· ·; zp}所导出的子图上的限制给出. 证毕.FCD86179-7F39-4C2E-AD6D-ACE81DE4BD3A

[参考文献]

[1]HARARY  F，  PLANTHOLT  M. The  Point-Distinguishing  Chromatic  Index [M]//HARARY  F，  MAYBEE  J  S. Graphs  and Application. New York： Wiley Interscience， 1985：147-162.

[2]HOR??K M， SOT?K R. The fifth jump of the point-distinguishing chromatic index of Kn;n   [J]. Ars Combinatoria， 1996， 42：233-242.

[3]HOR??K M， SOT?K R. Localization jumps of the point-distinguishing chromatic index of  Kn;n   [J]. Discuss Math Graph Theory， 1997， 17：243-251.

[4]HOR??K M， ZAGAGLIA SALVI N. On the point-distinguishing chromatic index of Km;n   [J]. Ars Combinatoria， 2006， 80：75-85.

[5]ZAGAGLIA SALVI N. On the value of the point-distinguishing chromatic index of Kn;n   [J]. Ars Combinatoria， 1990， 29B：235-244.

[6]CHEN X E. Point-distinguishing chromatic index of the union of paths [J]. Czechoslovak Mathematical Journal， 2014， 64（3）：620-640.

[7]CHEN  X  E，  GAO  Y  P，  YAO  B. Vertex-distinguishing  IE-total  colorings  of  complete  bipartite  graphs  Km;n（m < n）  [J]. Discussiones Mathematicae Graph Theory， 2013， 33（2）：289-306.

[8]LIU C J， ZHU E Q. General vertex-distinguishing total coloring of graphs [J]. Journal of Applied Mathematics， 2014：849748.

[9]牟亚蓉， 刘信生， 姚兵.基于含圈非连通图优美性的拓扑图密码[J].华东师范大学学报（自然科学版）， 2020（1）：51-57.

[10]任韩， 吴昊.图的空间理论：与图有关的线性代数理论（下）[J].华东师范大学学报（自然科学版）， 2012（6）：139-156.

[11]杨芳， 王治文， 陈祥恩， 等.完全图和星的合成的点可区别正常边染色[J].华东师范大学学报（自然科学版）， 2013（5）：136-143.

[12]張爽. K2;n;p 的点可区别IE-全染色及一般全染色（2? n ?5; n ? p）  [D].兰州：西北师范大学， 2020.

（责任编辑：陈丽贞）FCD86179-7F39-4C2E-AD6D-ACE81DE4BD3A