关于双圈图的动态色数

尚华辉，闫晓芳，苗连英

(1.中国矿业大学 数学系，江苏 徐州 221008；2.永城职业学院 基础部，河南 永城 476600)

本文研究的是有限、无向且连通的简单图。给定图G，分别用V(G)、E(G)表示G的顶点集、边集。对图G中任意顶点v，分别用d(v)、N(v)表示v的度数、邻点的集合。用Cn表示包含n个顶点的圈，其余概念参见文献[1].

图G的色数χ(G)是指对图G的顶点进行染色，使得任意2个相邻的顶点染不同颜色所需要的最少颜色数。G的动态染色是从顶点集到颜色集的一个映射，且满足下列2个条件：

1) 如果uv∈E(G)，则c(u)≠c(v)；

2) 对任意的顶点v∈V(G)，|c(N(v))|≥min{2,d(v)}.如果用k种颜色可以得到图G的一个动态染色，则称G有一个动态k-染色(或称G是动态k-可染的)。动态色数χd(G)是使得G有一个动态k-染色的最小的k.

动态染色是在文献[2]中提出来的。在文献[3]中进行了更深入地研究，证明了χd(G)≤Δ+3，并给出了树、圈、二分图、完全二分图,以及完全多部图的动态色数。文献[4]给出了Halin图和Series-Parallel图的动态色数，文献[5]给出了单圈图和大部分双圈图的动态色数。设T是p(p≥3)阶树，将T中某2个不相邻的点用一条新的边连接起来，得到的p阶含有p条边的图称为单圈图。或者说，恰含有1个圈的连通图称为单圈图。双圈图是指边数比顶点数多1的简单连通图。文献[5]没有给出当两个双圈有公共路时且公共路上有悬挂分支的这一较复杂情况。本文通过构造3个子图，解决了这种情况下的双圈图的动态色数，从而彻底解决了双圈图的动态色数问题。

1 主要引理

引理1[2]设G是一个连通的非平凡图，则χd(K2)=2.除此之外χd(K2)≥3.

引理2[2]除了K1和K2，任何树G的χd(G)=3.

设双圈图G上的两个圈分别为C1和C2.按照圈C1和C2相交的情况，将双圈图分为相交双圈图、无交双圈图和有公共路的双圈图。

在G中，构造了两个子图H1，H2，通过研究H1，H2的动态色数来刻画G的动态色数，见参考文献[5].

引理4[5]设G是用上述方法构造的双圈图G的子图，则

χd(G)=max{χd(H1),χd(H2)} .

2 主要结果及其证明

在给出主要结果之前,先做一些说明。

设G为双圈图，与G中的两圈相关联的连通分支(包含圈上的相应点，该点称为附着顶点)称为双圈图G的悬挂分支。显然双圈图的任何悬挂分支都是树。

除非特别说明，下文中的路均是指始点和终点在图G中的度均大于2，路上中间各点的度均为2.比如路(ui,uj)表示一条uiu1u2…umuj路，则路(ui,uj)的长度为m+1，且d(ui)>2，d(uj)>2，d(ut)=2，(t=1,2,…,m).若设c(ui)=1，c(u1)=2，则用1,2,3等3种颜色给(ui,uj)染色时，u2,u3,…,um,uj染的颜色顺序必是3,1,2,3,1,2,3,….即给定其中一端相邻两点确定的颜色后，其它点的颜色是被唯一确定的。根据以上染色过程，可以得出如下结论。

结论1 若(ui,uj)的长为3s+1(s=0,1,2,…)或3t+2(t=0,1,2,…)，且存在染色使得点ui,u1,u2,…,um,uj都满足动态染色的要求，则c(ui)≠c(uj).

结论2 若2条长为3s+1(s=0,1,2,…)或3t+2(t=0,1,2,…)的路首尾相邻于某顶点v，并把顶点v上原有的悬挂分支加上，形成的图(G的子图)的始点和终点的颜色可以相同也可以不同。

比如(ui,uj)的长为3s+1(s=0,1,2,…)或者3t+2(t=0,1,2,…)，路(uj,uk)的长为3s+1(s=0,1,2,…)或者3t+2(t=0,1,2,…)，注意到两路的连接点uj上一定存在悬挂分支，通过适当调整悬挂分支的染色可以使c(ui)≠c(uk)或c(ui)=c(uk).

结论3 若(ui,uj)的长为3s(s=0,1,2,…)，且存在1个染色使得此路上的ui,u1,u2,…,um,uj点都满足动态染色的要求，则必有c(ui)=c(uj).

结论4 若2条以上(包含2条)为3s(s=0,1,2,…)的路首尾相邻于某顶点v，并把顶点v上原有的悬挂分支加上，形成的图(G的子图)的始点和终点的颜色还相同。

比如(ui,uj)的长为3s(s=0,1,2,…)，路(uj,uk)的长为3t(t=0,1,2,…).无论怎样调整悬挂分支的染色，必有c(ui)=c(uk).

下面研究当2个双圈有公共路时且公共路上有悬挂分支的双圈图的动态色数。

设公共路Pm上的点依次为v1,v2,…,vm-1,vm,C1,C2表示图G中的2个圈。为了证明的需要，标记如下子图：C'1=C1-{v2,v3,…,vm-1},C'2=C2-{v2,v3,…,vm-1}，用r表示路C'1=C1-{v2,v3,…,vm-1}上被附着的悬挂分支分成的路长为3s+1(s=0,1,2,…)或者3t+2(t=0,1,2,…)的路的个数，用t表示路C'2=C2-{v2,v3,…,vm-1}上被附着的悬挂分支分成的路长为3s+1(s=0,1,2,…)或者3t+2(t=0,1,2,…)路的个数，用p表示路Pm上被附着的悬挂分支分成的路长为3s+1(s=0,1,2,…)或者3t+2(t=0,1,2,…)路的个数。不妨设r≥t，在上面的构造和分析的基础上,将证明本文的主要结论。

定理1 若图G是双圈图，双圈C1，C2有公共路Pm且公共路上有悬挂分支，则有

否则χd(G)=4.

证明：设图C'表示路C'1,C'2及其路C'1,C'2上所有附着的悬挂分支构成的图。不失一般性，记Pm中v1的颜色为c(v1)=1.根据路C'1,C'2的对称性，只需证r≥t时的情况。

情况1 当r=t=0时，由结论3可知，用3种颜色1，2，3可以满足图G'的动态染色的要求且有c(v1)=c(vm)；又由引理1可知χd(G')≥3.基于此，考察G是否是动态3-可染的，现只需考察3种颜色1，2，3在满足G'动态可染的基础上考察路Pm上点v2,v3,…,vm-1的染色。

1) 当p=0或者p≥2时，用颜色1,2,3满足G'且满足Pm上v1,v2,…,vm-1,vm各顶点的动态染色的要求，且满足c(v1)=c(vm).故χd(G)=3.

2) 当p=1时，由结论1知用颜色1,2,3同时满足Pm上v1,v2,…,vm-1,vm必有c(v1)≠c(vm)，与为了满足G'而必有c(v1)=c(vm)矛盾，故χd(G)≥4.易验证用4种颜色染能满足要求，故动态色数χd(G)=4.

情况2 当s=1且t=0时，在图G'中，用颜色1,2,3为满足C'1=C1-{v2,v3,…,vm-1}的动态染色需要c(v1)≠c(vm)，而为满足C'2=C2-{v2,v3,…,vm-1}需要c(v1)=c(vm)，故χd(G')≥4.易验证不论p的取值如何，用4种颜色能满足图G动态染色的要求。故动态色数χd(G)=4.

由结论3知，G'中的长为形如3s(s=1,2,…)的路对G'及其G的色数无影响，故下面的证明过程中，不妨设G'中不存在这样的路。

情况3 当s=t=1时，此情况下C'1=C1-{v2,v3,…,vm-1},C'2=C2-{v2,v3,…,vm-1}是2条路，且路中间的顶点上无附着悬挂分支。不妨记2条路分别为P1,P2.下面根据路P1与P2的阶数差的绝对值‖V(P1)|-|V(P2)‖来讨论：

1) 当‖V(P1)|-|V(P2)‖=0(mod3)时，这种情况下v1，vm上是否附着悬挂分支对整个图的色数时有影响的，故根据v1,vm上悬挂分支的数量来讨论当2顶点v1,vm中至少存在一顶点上附着有悬挂分支，则易验证适当调整分支的颜色，满足G'是动态-3可染的，结合引理1知χd(G')=3，且有c(v1)≠c(vm).接下来根据Pm上p的大小讨论G的动态色数。

a.当p≥1时，在图G'中，用颜色1,2,3给G'染色时，v1或vm在C'1=C1-{v2,v3,…,vm-1}和C'2=C2-{v2,v3,…,vm-1}中的邻点所染的颜色可能相同，但适当调整v1,vm上悬挂分支的颜色分支来调整v1或者vm在图G中的邻点集的色数(当p≥2时，也可以调整v2,v3,…,vm-1上的分支色数来配合G整个的动态色数)使Pm上的v2,v3,…,vm-1也满足动态3-染色的要求，故χd(G)=3.

b.当p=0时，用颜色1,2,3给Pm染色时，必有c(v1)=c(vm)，与用颜色1,2,3能满足G'动态3-染色矛盾(因为用颜色1,2,3给G'动态染色时必有c(v1)≠c(vm))，与是否有悬挂分支无关，故χd(G)≥4.易验证4种颜色能满足G的动态染色的要求，故χd(G)=4.

2) 当‖V(P1)|-|V(P2)‖≠0(mod3)时，注意到此时的G'除去其上的所有悬挂分支就是一个长度为3s(s=2,3,…)的圈。故由引理3知用颜色1,2,3可满足其动态染色的要求，由结论4知：G'也满足是动态3-可染的，且必有c(v1)≠c(vm).故考察G是否是动态3-染色的，只需考察路Pm上的染色。

a. 若p≥1，由引理1知，3种颜色能满足Pm是动态3-染色的，故χd(G)=3.

b.p=0，不论v1,vm上是否有悬挂分支对路Pm的动态色数没有本质的影响，即动态染Pm需要4种不同的颜色，故χd(G)≥4，易验证用4种颜色满足图G其动态染色要求，即有χd(G)=4.

情况4 若C'1=C1-{v2,v3,…,vm-1}中的m≥2,C'2=C2-{v2,v3,…,vm-1}中的n≥1,其中(m≥n).同上述情况2)类似讨论可得：

若p≥1,则χd(G)=3；若p=0,则χd(G)=4.

至此，完成了定理1的证明。

文献[5]给出了一个不能用引理4判定其动态色数的例子，但易见可用定理1得出其动态色数。上述定理包含引理4的的第一和第三种情况：不难看出相交双圈图可以看成是有公共路双圈图当公共路Pm上的p=0时的特殊情况；从上述证明过程可得：可把有公共路且没有悬挂分支的双圈图的情形看成公共路仅被悬挂分支分成一部分即可。