三星的最优的一般点可区别全染色

李 婷，陈祥恩，王治文

（1.西北师范大学数学与统计学院，甘肃 兰州 730070；2.宁夏大学数学计算机科学学院，宁厦 银川 750021）

0 引言及准备工作

点可区别一般边染色是由Harary F等人于1985年在文献[1]中提出的，在文献[1-4]中均有研究.近些年来点可区别的未必正常的全染色也逐渐被研究.例如，点可区别IE-全染色在文献[5]中被提出，而一般点可区别全染色在文献[6]中被提出.

G 的 k-一般全染色 f是指从 V（G）∪E（G）到{1，2，…，k}的一个映射.

设f是G的一个一般全染色，若对图G的任意两个不同的顶点u，v，有C（u）≠C（v），则f称为图G的一般点可区别全染色（GVDTC）.

图G的使用k种颜色的一般点可区别全染色称为图G的k-一般点可区别全染色（简记为k-GVDTC）.令图G存在k-GVDTC}，则称χgvt（G）为G的一般点可区别全色数.

星Sn就是完全二部图K1，n（n≥1）.称Sm，n是双星，如果Sm，n是树，并且顶点集为边集为其中 m，n 是正整数且均大于 1.称 Sp，q，r是三星，如果 Sp，q，r是树，并且顶点集为边集为v0w0}，其中 p，q，r是正整数.

文献[6]中研究了路，圈，星（即K1，n），双星，三星，轮，扇，完全图的一般点可区别全染色，确定了它们的一般点可区别全色数.但未给出三星的一般点可区别全色数这一结论的详细证明，仅指出了思路.在本文中，我们将用一种不同于文献[6]中指出的思路给出三星的最优的一般点可区别全染色.

引理1[6]设Sn（n≥1）是一个星，则有

事实2设图G有k-GVDTC，但图G没有（k-1）-GVDTC，则χgvt（G）＝k.

1 主要结果及其证明

定理 3 设 Sp，q，r是一个三星，令 l＝p＋q＋r，则

证明：当l＝3时，显然χgvt（S1，1，1）≥3.因为2种颜色只能区别3个点，而图1（a）给出了S1，1，1的3-GVDTC，因此χgvt（S1，1，1）＝3.

图 1 S1，1，1，S1，1，2，S1，2，1 的3-GVDTC

当 l＝4 时，只需考虑 S1，1，2，S1，2，1即可.显然对这 2 个图，χgvt≥3.因为 2 种颜色只能区别3个点，而图1中（b），（c）分别给出了这2个图的3-GVDTC，因此χgvt（S1，1，2）＝χgvt（S1，2，1）＝3.

当 l＝5 时，只需考虑 S1，1，3，S1，3，1，S1，2，2，S2，1，2即可.显然对这 4 个图，χgvt≥4.因为3种颜色只能区分7个点，而图2分别给出了这4个图的4-GVDTC，故χgvt（S1，1，3）＝χgvt（S1，3，1）＝χgvt（S1，2，2）＝χgvt（S2，1，2）＝4.

当 l＝6 时，只需考虑 S1，1，4，S1，4，1，S1，2，3，S1，3，2，S2，1，3，S2，2，2即可.显然对这 6 个图，χgvt≥4.因为3种颜色只能区分7个点，而图3分别给出了这6个图的4-GVDTC，故χgvt（S1，1，4）＝χgvt（S1，4，1）＝χgvt（S1，2，3）＝χgvt（S1，3，2）＝χgvt（S2，1，3）＝χgvt（S2，2，2）＝4.

图 2 S1，1，3，S1，3，1，S1，2，2，S2，1，2 的4-GVDTC

图 3 S1，1，4，S1，4，1，S1，2，3，S1，3，2，S2，1，3，S2，2，2 的4-GVDTC

以下假设l≥7.

小正整数.设u1，u2，u3是 Sp，q，r中度大于 1 的那 3 个顶点，Sp，q，r中与 u1相邻的悬挂点为u1，1，…，u1，p；与 u2相邻的悬挂点为 u2，1，…，u2，q；与 u3相邻的悬挂点为u3，1，…，u3，r.

设 G′是从 Sp，q，r中删去 2 条边 u1u2，u2u3后再将 3 个顶点 u1，u2，u3等同所得的图，则G′是阶为l＋1的星，即G′≅Sl，令w为G′的中心.由引理1知，Sl有k-GVDTC g，则G′也有k-GVDTC g，且不妨设G′的l条悬挂边wu1，1到wu3，r的颜色是按从小到大的顺序排列.下构造 Sp，q，r的 k-GVDTC f.

让 Sp，q，r的悬挂点 u1，i沿袭在 g 下 G′中对应的悬挂点 u1，i的颜色，i＝1，2，…，p；让 Sp，q，r的悬挂点 u2，j沿袭在 g 下 G′中对应的悬挂点 u2，j的颜色，j＝1，2，…，q；让 Sp，q，r的悬挂点u3，t沿袭在 g 下 G′中对应的悬挂点 u3，t的颜色，t＝1，2，…，r；让 Sp，q，r的悬挂边 u1u1，i沿袭在 g 下 G′中对应的悬挂边 wu1，i的颜色，i＝1，2，…，p；让 Sp，q，r的悬挂边 u2u2，j沿袭在g 下 G′中对应的悬挂边 wu2，j的颜色，j＝1，2，…，q；让 Sp，q，r的悬挂边 u3u3，t沿袭在 g 下G′中对应的悬挂边 wu3，t的颜色，t＝1，2，…，r.则在此基础上以下只需考虑 u1，u1u2，u2，u2u3，u3的染色即可.

令A（ui）表示与ui关联的悬挂边的颜色构成的集合（非多重集），i＝1，2，3.以下分4种情况讨论.

在这种情况下，可按图4 中（a），（b），（c）所给出的方式分 3 种情形对 u1，u1u2，u2，u2u3，u3进行染色.比如：在情形（a）中，点 u1，u2，u3分别用 2，4，4 去染；边 u1u2，u2u3分别用 3，2染.这时，C（u1）＝{1，2，3}，C（u2）＝{1，2，3，4}，C（u3）＝{1，2，4}，其它顶点即悬挂点的色集合为1-子集或2-子集，因此所得的染色是k-GVDTC.在其他情形下，都可类似得到最终染色是k-GVDTC，且不再赘述.

图4 情况（1）的示意图

情形（a）记为情形（1，1，1），情形（b）记为情形（1，1，2），情形（c）记为情形（1，2，3），除这 3种情形外，还有情形（1，2，2）等价于情形（b）.

注记：上图均为示意图，在上图中只标出了与u1，u2，u3关联的悬挂边颜色的种类，而与u1，u2，u3关联的悬挂边的条数不仅仅只有图中出现的条数.后面再出现时，不再作注解.

我们将图 5中的情形（a）记为情形（1，1，12），情形（b）记为情形（1，1，23），其它类似.除上述 7种情形外，还有情形（12，2，2）与情形（a）等价；情形（12，3，3）与情形（b）等价；情形（12，2，3）与情形（c）等价；情形（12，3，4）与情形（d）等价；情形（1，23，3）与情形（f）等价.因此，出现的这些情形将不再画图表示.

由悬挂边染色规律可得，A（u2）≠A（u3），则 A（u3）A（u2）≠ø且 A（u2）A（u3）≠ø.设a，b∈A（u2），a＜b 且 a∉A（u3），c，d∈A（u3），c＜d 且 d∉A（u2）.

图5 情况（2）的示意图

我们用 d染u1；用{1，2，…，k}{c，d}中的两种不同的颜色分别去染 u2u3与u3；用{1，2，…，k}{A（u1）∪{d}}中某种颜色去染 u1u2；用{1，2，…，k}{a，b，d}中某种颜色去染 u2.

由悬挂边染色规律可得，A（u1）≠A（u3），则 A（u3）A（u1）≠ø且 A（u1）A（u3）≠ø.设a，b∈A（u1），a＜b 且 a∉A（u3），c，d∈A（u3），c＜d 且 d∉A（u1）.

我们用 d染u2；用{1，2，…，k}{c，d}中的两种不同的颜色分别去染 u2u3与 u3；当A（u2）＝{f（u2u3）}时，用{1，2，…，k}{d，f（u2u3）}中的某种颜色去染u1u2；当A（u2）≠{f（u2u3）}时，用 f（u2u3）去染 u1u2；用{1，2，…，k}{a，b，d}中某种颜色去染 u1.

由悬挂边染色规律可得 A（u1），A（u2），A（u3）互不相同.设 a，b∈A（u1），a＜b 这时只需用颜色k分别去染u1，u2，u1u2，u2u3；再用a染u3即可.显然最终所得的染色是Sp，q，r的k-GVDTC.

综上可得 Sp，q，r的 k-GVDTC f.

2 结语

本文定理2是在文献[6]定理9的基础上用一种更为优化的方法探讨并证明了三星具有一般点可区别全染色.另外，三星在3-阶的路的基础上加悬挂点得到的，那么这种方法是不是可以继续延续下去，进而得到在n-阶的路上加悬挂点所得的图的一般点可区别全色数？这就是今后需要继续研究的课题.