某些顶点对被非多重色集合所区别的未必正常染色的综述

(西北师范大学 数学与统计学院, 甘肃 兰州 730070)

1 引言及准备工作

本文所考虑的图均为有限无向简单图. 关于图的可区别的正常边染色和全染色, 可以参看文献[1]. 在这篇综述文章里, 重点介绍了图的被非多重色集合可区别的未必正常的边染色和全染色.

所谓图G的一个一般全染色是指若干种颜色对图G的全体顶点及所有边的一个分配. 注意, 这里并不要求下面的三个条件成立:

V-条件: 任意两个相邻的顶点被分配以不同的颜色;

I-条件: 任意一条边与其(每个)端点被分配以不同的颜色;

E-条件: 任意两条相邻的边被分配以不同的颜色.

图G的一个满足V-条件[分别的,I-条件,E-条件]的一般全染色称为图G的IE-全染色[分别的,VE-全染色,VI-全染色]; 图G的一个同时满足V-条件及I-条件[分别的,V-条件及E-条件,I-条件及E-条件]的一般全染色称为图G的E-全染色[分别的,I-全染色,V-全染色]. 使用了k种颜色的一般全染色[分别的,V-,I-,E-,VI-,VE-,IE-全染色]叫做k-一般全染色[分别的,k-V-,k-I-,k-E-,k-VI-,k-VE-,k-IE-全染色]. 这7种染色统称为未必正常的全染色. 如果没有特别说明, 在提及使用了k种颜色时, 通常认为所使用的颜色为1, 2, …,k. 对图G的任意一个未必正常的全染色f及任一z∈V(G)∪E(G), 将z在f下的颜色记为f(z). 图G的一个k-一般全染色f也经常被定义为一个映射f:V(G)∪E(G)→{1, 2, …,k}. 图G的一个使用了k种颜色的其他 6 种未必正常全染色也经常以满足相应的各种不同条件的映射f:V(G)∪E(G)→{1, 2, …,k}的形式来定义.

一个图的正常全染色(即同时满足V-条件,I-条件,E-条件的一般全染色)及7种未必正常全染色之间的关系见图 1, 对每条箭线来说, 箭尾处的染色一定是箭头处的染色, 反之未必.

图1 正常全染色及7种未必正常全染色之间的关系Fig.1 The relation among proper total coloring and 7 types of not necessarily proper total colorings

在某个未必正常染色下两个顶点被非多重色集合[分别的, 多重色集合, 色和, 色积, 模色和]所区别是指这两个顶点在所给染色下的非多重色集合[分别的, 多重色集合, 色和, 色积, 模色和]不同.

本文涉及的顶点被区别的方式为被非多重色集合所区别. 按照区别的对象分为：任意两个不同顶点被区别, 任意两个相邻顶点被区别, 亦或是任意两个距离不超过d的不同顶点被区别. 我们提到的边染色及全染色都是未必正常的.

2 点可区别一般边染色

设f是图G的一个一般边染色. 如果对图G的任意两个不同顶点u和v, 都有S(u)≠S(v), 那么f称为是点可区别的. 对图G进行点可区别一般边染色所需最少颜色的数目记为0(G), 称为图G的点可区别一般边色数. 这种染色是由 Harary等[2]于1985年提出的，这是最早的有关可区别染色的文献. 因此有理由认为 Harary等是可区别染色的开创者. 该文对“点可区别”采用了“point distinguishing”的书写方式. 当图G含有至少两个孤立点或含孤立边时, 规定0(G)=∞. 该文给出了如下结论：

▷ 若H是图G的生成子图, 则0(G)≤0(H)+1.

▷设图G的阶为n, 则0(G)≥log2n.

▷对于阶为n的路Pn(n≥3), 有

▷对于阶为n的圈Cn, 有

▷对于阶为n的Hamilton图G, 有

▷对于阶为n(n≥3)的完全图Kn, 有0(Kn)=「log2n⎤+1.

▷当m≤n且m≥「log2n⎤+1时, 有0(Km, n)≤「log2n⎤+2.

▷ 设n≥2, 则「log2n⎤+1≤0(Kn, n)≤「log2n⎤+2.

▷ 设Qn为n维超立方,n≥2, 则0(Qn)=n+1.

确定完全二部图的点可区别一般边色数十分困难. 已经取得了许多成果参见文献[3-7]. 在文献[8]中, 作者提出了一个指标. 设G是一个vdec图(即最多含一个孤立点且不含孤立边的图). 让ni(G)表示图G的度为i的顶点数目,δ≤i≤Δ, 这里δ与 Δ分别表示图G的最小度与最大度. 当G有一个孤立点时, 令

否则, 当G没有孤立点时, 令

文献[8]中给出了p条阶至少为 3 的路的不交并能够用2p+r种颜色(r为非负整数) 进行点可区别一般边染色的充分必要条件, 并给出了结论: 当G为若干条阶至少为 3 的不交路时, 有0(G)=ρ(G)或ρ(G)+1. 基于已有结论和事实0(3C3)=ρ(3C3)+2, 该文提出了如下猜想.

VDGEC猜想[8]如果G是一个vdec图, 则ρ(G)≤0(G)≤ρ(G)+2. 此外

3 邻点可区别一般边染色

设f是图G的一个一般边染色. 如果对图G的任意两个相邻顶点u和v, 都有S(u)≠S(v), 那么f称为是邻点可区别的. 对图G进行邻点可区别一般边染色所需的最少颜色的数目记为gndi(G)或者称为图G的邻点可区别一般边色数. 这种染色是由Györi等[9]于2008年提出的.在文献[9]中得到了“至少含两条边的连通二部图的邻点可区别一般边色数不超过3”. 在文献[10]中给出下述结论.

定理[10]若G是无孤立边的图, 且其(正常点)色数至少为3, 则(G)⎤+1.

其他相关成果可见参考文献[11-14].

4 D(d)-点可区别一般边染色

文献[15]中引入了图的D(d)-点可区别一般边染色.设d是正整数, 如果∀u,v∈V(G),一旦1≤dG(u,v)≤d, 都有S(u)≠S(v), 那么f称为G的使用了k种色的D(d)-点可区别一般边染色, 对一个图G进行D(d)-点可区别一般边染色所需的最少颜色数称为图G的D(d)-点可区别一般边色数, 记为

文献[15]中对d=2的情形做了讨论,得到了路、圈、星、双星、扇、轮的D(2)-点可区别一般边色数, 基于此, 提出了一个猜想.

对阶不小于 3 的连通图G, 令mi表示图G中使得任意两点间的距离不超过d的度不超过i的顶点的最大数目,i=δ,δ+1, …,Δ, 且记

D(2)-VDGEC猜想[15]如果G是阶至少为 3 的连通图, 那么μ′2(G)≤

设图G为连通图, 其 2 距离色数2(G)=4, 称G的一个以X,Y,Z,W为色类的 2 距离 4 着色是稳定的 (色类是指在图的顶点着色下染同一种颜色的所有顶点组成的集合), 如果对W中任意 2 度顶点w, 设u,v为w的邻点, 有

(i)当d(u)=1,d(v)=3时,v的 除w之外的两个邻点至少有一个为1度;

(ii)当d(u)>1且d(v)>1时, 若u,v∈X∪Y, 则在X∪Y中任意一个与w的距离为1或2的点在Z中有邻点;若u,v∈X∪Z, 则在X∪Z中任意一个与w的距离为1或2的点在Y中有邻点; 若u,v∈Y∪Z, 则在Y∪Z中任意一个与w的距离为1或2 的点在X中有邻点.

文献[15]中对于2距离色数等于3及4的图的D(2)-点可区别一般边色数做了探讨,得到了具有稳定2距离4着色的连通图的D(2)-点可区别一般边染色为3的结论, 同时提出了一个公开问题.

公开问题是否对任意使得2(G)=4的连通图G都存在稳定的2距离4着色?

5 点可区别的各种未必正常的全染色

设f为图G的V-全染色(分别的,E-,I-,VE-,VI-,IE-全染色,一般全染色). 如果对∀u,v∈V,u≠v, 总有C(u)≠C(v), 则称f为点可区别的. 使用了k种颜色的点可区别V-全染色简记为k-VDVTC. 类似的有k-VDETC,k-VDITC,k-VDVETC,k-VDVITC,k-VDIETC,k-VDGTC.

对一个图G进行点可区别V-全染色(分别的, 点可区别E-,I-,VE-,VI-,IE-, 一般全染色)所需的最少颜色数目称为图G的点可区别V-全色数(分别的, 点可区别E-,I-,VE-,VI-,IE-, 一般全色数), 记为(分别的,,gvt(G)). 比如

图2 7种点可区别的未必正常的全色数及点可区别正常全色数之间的关系

Fig.2 The relation among 7 types of vertex-distinguishing of not necessarily proper total colorings and vertex-distinguishing proper total coloring

对于图G, 用ni(G)或ni表示图G的度为i的顶点个数,δ≤i≤Δ, 这里δ与Δ分别表示图G的最小度和最大度.记

显然有ζ(G)≤

文献[16]首次提出图的点可区别I-全染色及图的点可区别VI-全染色, 并且确定了完全图、完全二部图、轮、扇、2个顶点是最大度顶点(它们相邻)，而其余所有顶点为悬挂点的双星、路、圈、两条同阶圈的联图、一类近完全图等图类的点可区别I-全色数以及点可区别VI-全色数, 并提出了下面的猜想.

VDITC猜想或ζ(G)+1.

VDVITC猜想或ζ(G)+1.

自然地,VDITC猜想的成立就可推出VDVITC猜想的成立.文献[17-19]已对两条路的联图、圈与路的联图、圈与圈、圈与轮、圈与扇的联图的点可区别I-全染色和点可区别VI-全染色进行了研究. 张生桂已对完全图删去一个完美匹配的边或一个近完美匹配的边所得到的图,nC3mC3,nC4mC4给出其点可区别I-全色数和点可区别VI-全色数. 杨晗已对mC3,mC4给出其点可区别I-全色数和点可区别VI-全色数. 结论均支持相关猜想.

文献[20]中探讨了完全图、完全二部图K2, n、 星、轮、扇、路和圈的VDETC, 提出了指标η(G)及两个猜想. 对一个不含孤立顶点的图G, 令

VDETC第一猜想对一个没有孤立顶点且色数至多为5的图G, 我们有或η(G)+1.

VDETC第二猜想对一个没有孤立顶点的图G, 我们有(G)}.

文献[21]中得出了mC3和mC4的点可区别E-全色数. 文献[22-25]中完全讨论了完全二部图K3,n,K4,n,K5,n的VDETC,文献[26-28]讨论了完全二部图K6,n与K7,n的点可区别E-全染色. 包丽娅等[29]已分别对完全二部图K8,n、K9,n与K10,n的点可区别E-全染色进行了探讨.

文献[30-31]已对路、圈、完全图、轮、扇及完全二部图K1,n,K2,n的点可区别VE-全染色进行了研究, 确定了它们的点可区别VE-全色数. 据此分析提出了如下猜想.

VDVETC猜想对一个没有孤立顶点的图G, 我们有或η(G)+1.

师志凤[32]确定了完全二部图K6,n的点可区别E-全色数及点可区别VE-全色数, 结论表明VDETC猜想和VDVETC猜想对于完全二部图K6,n是成立的.

文献[33-37]对图的点可区别IE-全染色进行了研究. 在文献[33]中提出了一个指标和三个猜想. 令

VDIETC第一猜想对一个简单图G, 如果它的(正常点)色数(G)≤4, 则或ξ(G)+1.

VDIETC第二猜想对一个简单图G, 我们有(G)}.

VDIETC第三猜想设s使得2s-1≥3m的最小正整数. 当2r-2m-1

关于VDIETC第三猜想, 师瑾[38]给出了“r=m-4,m-3,m-2,s≤m-2”时的证明.

Liu等[39]提出了一般点可区别全染色(简记为GVDTC), 这一概念就是本文已经定义的点可区别一般全染色(简记为VDGTC). 一般点可区别全色数实际上就是本文已经定义的点可区别一般全色数, 记为gvt(G), 这里沿用了文献[39]中的记号.

文献[39]中研究了路、圈、星(K1,n)、双星、三星、轮、扇、完全图的一般点可区别全染色, 确定了它们的一般点可区别全色数. 比如

命题[39]设Sn是一个n+1阶星,n≥1, 则

基于此, 文献[40-41]中对一类含有4-圈的单圈图、2K2K1的冠图的一般点可区别全色数被确定. 李婷[42]还确定一类分别含3-圈、4-圈、5-圈的单圈图, 以及P4、P5、K4的冠图的一般点可区别全色数. 在文献[43]中三星的一般点可区别全色数的结论被给出了详证.在文献[44]中探讨了K4, n与K5, n的一般点可区别全色数.

在文献[45-47]中寇艳芳等对完全三部图K1,n,p的点可区别的IE-全染色及点可区别的一般全染色进行了研究. 笔者指导的研究生张爽、杨佳睿、马静静分别对完全三部图K2,n,p,K3,n,p,K4,n,p的点可区别IE-全染色及点可区别的一般全染色进行了探讨.

对完全二部图的VDETC,VDVETC,VDIETC,VDGTC的研究具有极大的难度, 因为这四种染色不要求边染色正常. 这就如同确定完全二部图的点可区别一般边色数极为困难一样.

根据已有的结论, 我们提出如下猜想.

VDGTC猜想对一个简单图G, 有gvt(G)=ξ(G)或ξ(G)+1.

马宝林对路、圈、轮、扇、完全图、mC3、mC4等图类的点可区别V-全色数进行了探索, 发现绝大多数情况下都与相应图的点可区别正常全色数相同. 从而提出如下猜想.

何玉萍[48]发现了对于图mC6,mC7,mC8,mC9来说,VDVTC猜想是成立的.

6 邻点可区别的各种未必正常的全染色

设f为图G的V-全染色(分别的,E-,I-,VE-,VI-,IE-全染色,一般全染色). 若对∀u,v∈V(G), 一旦uv∈E(G),就有C(u)≠C(v), 则称f为邻点可区别的. 使用了k种颜色的邻点可区别V-全染色简记为k-AVDVTC. 类似的有k-AVDETC,k-AVDITC,k-AVDVETC,k-AVDVITC,k-AVDIETC,k-AVDGTC.

对一个图G进行邻点可区别V-全染色(分别的, 邻点可区别E-,I-,VE-,VI-,IE-, 一般全染色)所需的最少颜色数目称为图G的邻点可区别V-全色数(分别的, 邻点可区别E-,I-,VE-,VI-,IE-, 一般全色数), 记为分别的,,

这7种邻点可区别的未必正常的全色数及邻点可区别正常全色数at(G)之间有类比于图 2 所示的关系.

在文献[49]中得到下述结论：

▷若G是非空二部图, 则

▷设G是一个色数为 3 的图. 则G的邻点可区别E-全色数等于 3 的充分必要条件是存在G的正常 3- 染色h, 使得不存在长为3的迹u1u2u3u4, 使u1,u2,u3在h下的色不同， 而u1,u4在h下的色相同.

▷对没有孤立边的图G, 有′(G)≤′a(G), 这里′a(G)表示图G的邻点可区别正常边色数.

▷设n≥3, 则

▷对树T, 有

▷对任意非空图G, 有3≤(G)+1; 对任意非空二部图G, 有

▷对任意图G, 有「log2(G)⎤+1≤(G)⎤+2.

▷对任意的色数至少为 4 的图G, 有(G)+1)⎤+1.

▷对树T, 有

▷对至少 2 阶完全图Kn, 有

▷对任意图G, 有max{(G),′(G)}≤≤(G)+′(G).

▷设T是阶至少为 2 的树, 且T有两个最大度顶点相邻, 则

▷设T是阶至少为 4 的树, 且T的最大度顶点唯一或者任意两个最大度顶点不相邻, 则=Δ(T).

▷若n≥3, 则

文献[49]中提出如下三个猜想.

AVDVITC猜想对任意图G, 有

AVDVTC猜想对任意图G, 有

AVDITC猜想对任意图G, 有

显然,AVDVTC猜想与AVDITC猜想之一成立就可推出AVDVITC猜想成立.

公开问题是否存在使得(G)≥4,(G)是2的方幂,且(G)⎤+1成立的图.

文献[50]中确定了路、圈、星和扇的倍图的邻点可区别VI-全色数, 结论支持AVDVITC猜想. 文献[51-52]中分别确定了图的邻点可区别VI-全色数及图的邻点可区别V-全色数的上界. 文献[53]中确定了两类冠图Cm·Cn与Cm·Kn的邻点可区别I-全色数, 结论支持AVDITC猜想.

Huang等[54]将邻点可区别一般全色数记为″gnd(G), 而在文献[55] 中记为在文献[54]中给出了下列重要结论：

▷设G为阶至少为 2 的连通图. 则″gnd(G)=2当且仅当G是二部图.

▷若H为G的子图, 则″gnd(H)≤″gnd(G).

▷对没有孤立边且色数至少为 3 的图G, 有″gnd(G)=gndi(G).

在文献[56]中对一些特殊图类给出了最优邻点可区别一般全色数的算法实现.

7 D(d)-点可区别的各种未必正常的全染色

设f为图G的V-全染色(分别的,E-,I-,VE-,VI-,IE-全染色,一般全染色), 而d为正整数. 如果若对∀u,v∈V(G), 一旦1≤dG(u,v)≤d, 就有C(u)≠C(v), 则称f为D(d)-点可区别的. 使用了k种颜色的D(d)-点可区别V-全染色简记为k-D(d)-VDVTC. 类似的有k-D(d)-VDETC,k-D(d)-VDITC,k-D(d)-VDVETC,k-D(d)-VDVITC,k-D(d)-VDIETC,k-D(d)-VDGTC.

对一个图G进行D(d)-点可区别V-全染色(分别的,D(d)-点可区别E-,I-,VE-,VI-,IE-, 一般全染色)所需最少颜色的数目称为图G的D(d)-点可区别V-全色数(分别的,D(d)-点可区别E-,I-,VE-,VI-,IE-, 一般全色数), 记为(分别的,,

8 展 望

可区别染色的范围很广． 令

那么, 对任意X∈,Y∈,Z∈, 都可定义“X被Y所区别的Z染色”, 共有3×5×8=120种. 本文前面仅涉及到Y=“非多重色集合”的情况.

那么, 对任意X∈,Y∈1,Z∈1, 可定义“X被Y所区别的Z染色”. 比如让X=“任意两个相邻顶点”,Y=“扩展色和”,Z=“一般全”, 那么“X被Y所区别的Z染色”就是文献[58]中所提出的, 在文献[59-61]中均有研究.

针对每一种染色,可能研究的问题主要有: 确定一些具体图类的色数; 提出相应染色的猜想, 争取解决猜想, 或研究某类图是否满足猜想;给出相关色数的上界;研究某类图的色数随着阶增大的变化趋势;研究(可区别)染色的某个特定问题,比如寻找子图的色数不超过其母图相应色数的条件.希望对可区别染色理论感兴趣的学者能创新方法、开拓思路,做出优异成果.