广义Petersen图的2-hued着色

2022-11-28刘凤霞魏文娟

四川师范大学学报（自然科学版） 2022年6期

关键词：外圈正则着色

刘凤霞, 魏文娟

(新疆大学数学与系统科学学院, 新疆乌鲁木齐 830046)

1 引言与基本概念

图的着色理论是图论重要的研究领域之一,其结论在工程领域中都有广泛应用.本文只考虑简单有限图,没给出的术语和符号可参考文献[1].

设

G=(V(G),E(G))

是一个图,其中V(G)和E(G)分别表示图的顶点集和边集.顶点v∈V(G),图G中与顶点v关联的边的数目称为顶点v的度数,记为dG(v).顶点集V(G)中所有与顶点v相邻的顶点构成的集合称为顶点v的邻集,即

NG(v)={u|uv∈E(G),u∈V(G)}.

闭邻集记为

NG[v]=NG(v)∪{v}.

图G称为k-正则的,如果图G中任意v∈V(G)都有

dG(v)=k.

顶点子集S⊆V(G)的导出子图记为G[S].

图的r-hued着色的定义早期是在文献[2-3]中提出的.在文献[4-5]中,r-hued着色又被称为条件着色.特别地,当r=2时,在文献[4]中,2-hued着色被称为动态着色.2008年,Li等[6]研究了条件着色的算法复杂性;2012年,林妍等[7]研究了r-hued着色的蚁群算法,并且给出广义Petersen图和其他一些图类的这种算法，这使得研究条件着色更有意义.设k、r为正整数,图的一个(k,r)-着色是一个映射

φ:V(G)→C(k)={1,2,…,k}

满足以下2个条件：

(i) 若uv∈E(G),则φ(u)≠φ(v)；

(ii) 任意v∈V(G),有

|φ(NG(v))|≥min{dG(v),r}.

图的r-hued着色数是使得图G具有(k,r)-着色的最小正整数k,记为χr(G).

广义Petersen图记为Pn,t,它的顶点集和边集分别为:

V(G)={u1,u2,…,un;v1,v2,…,vn},

E(G)={uivi,uiui+1,vivi+t|1≤i≤n},

χ3(Pn,t)=4,

当且仅当n≡0(mod4),且t≡±1(mod4).

本文研究广义Petersen图的2-hued着色数.由广义Petersen图定义知,广义Petersen图为3-正则图.因此,要使得广义Petersen图满足(k,2)-着色的条件,则任意顶点v∈V(G),|φ(NG(v))|≥2且φ(v)与其邻点的着色不同,从而广义Petersen图的2-hued着色数χ2(Pn,t)≥3.关于图着色的Brooks定理[10]指出,若G是连通的简单图,并且它既不是奇圈又不是完全图，则

χ(G)≤Δ(G).

一般图的r-hued着色数的上界也被深入研究，文献[4]得到若G是Δ≤3的图,则χ2(G)≤5,并且等式成立当且仅当G=C5,而广义Petersen图是3-正则图且Pn,tC5,则χ2(Pn,t)≤4.因此

χ2(Pn,t)∈{3,4}.

关于一般图的r-hued着色数的更多结论可查阅文献[11-13].本文分别刻画2-hued着色数为3或4的广义Petersen图.

2 主要结论及证明

广义Petersen图是一类重要的图类,从文献[14]中可以看出其在图论研究中的重要作用.在广义Petersen图Pn,t中,设n与t的最大公约数为d,即(n,t)=d,则

V={v1,v2,…,vn}

定理 1若n≡0(mod3),t≡±1(mod3),则

χ2(Pn,t)=3.

证明已知χ2(Pn,t)≥3.下面构造一个广义Petersen图Pn,t的(3,2)-着色φ.定义映射

φ:V(Pn,t)→{a,b,c}

如下：

φ-1(a)={ui,vj|i≡1(mod3),j≡0(mod3)},

φ-1(b)={ui,vj|i≡2(mod3),j≡1(mod3)},

φ-1(c)={ui,vj|i≡0(mod3),j≡2(mod3)}.

因为n≡0(mod3),对任意ui∈{u1,u2,…,un},有

φ({ui-1,ui,ui+1})={a,b,c},

所以

|φ(NG(ui))|≥2.

对任意uivi∈E(G),有

φ(ui)≠φ(vi).

对任意vi∈{v1,v2,…,vn},当t≡1(mod3)时,有:

φ(vi+t)=φ(vi+1),φ(vi-t)=φ(vi-1);

当t≡-1(mod3)时,有:

φ(vi+t)=φ(vi+2)=φ(vi-1),

φ(vi-t)=φ(vi-2)=φ(vi+1).

因此

φ({vi,vi-t,vi+t})={a,b,c},

从而对任意vi∈{v1,v2,…,vn},有

|φ(NG(vi))|=2,

故φ是广义Petersen图Pn,t的一个(3,2)-着色,所以χ2(Pn,t)≤3.进一步,χ2(Pn,t)=3.综上所述,定理1得证.

由定理1,当n≡0(mod3)时,广义Petersen图Pn,t的2-hued着色数只剩t≡0(mod3)的情况没有刻画.下面这个定理将得到当n≡0(mod3)且t=3时,广义Petersen图的2-hued着色数.

定理 2若n≡0(mod3),t=3,则χ2(Pn,t)=3.

证明构造广义Petersen图Pn,t的一个(3,2)-着色φ.

φ:V(Pn,t)→{a,b,c}

如下：

φ-1(a)={ui,vj|i≡1(mod3),

j≡5(mod6),j≡0(mod6)};

φ-1(b)={ui,vj|i≡2(mod3),

j≡3(mod6),j≡4(mod6)};

φ-1(c)={ui,vj|i≡0(mod3),

j≡1(mod6),j≡2(mod6)}.

因为n≡0(mod3),所以由上述映射得对任意ui∈{u1,u2,…,un},有

φ({ui-1,ui,ui+1})={a,b,c},

故

|φ(NG(ui))|≥2.

进一步,对任意uivi∈E(G),有

φ(ui)≠φ(vi).

因为n≡0(mod3)且是偶数,所以对任意vi∈{v1,v2,…,vn},由映射得

φ(vi-3)=φ(vi+3).

又因为

φ(ui)≠φ(vi),

φ(ui)=φ(ui-3)=φ(ui+3),

所以

φ({vi,vi-t,vi+t,ui})={a,b,c},

从而对任意vi∈{v1,v2,…,vn},有

|φ(NG(vi))|≥2.

因此,在这种情况下,φ是广义Petersen图Pn,t的一个(3,2)-着色.

φ:V(Pn,t)→{a,b,c}

如下：

φ-1(a)={ui,vj|i,j≤n-6,i≡1(mod3),

j≡3(mod6),j≡5(mod6)};

φ-1(b)={ui,vj|i,j≤n-6,i≡2(mod3),

j≡0(mod6),j≡4(mod6)};

φ-1(c)={ui,vj|i,j≤n-6,i≡0(mod3),

j≡1(mod6),j≡2(mod6)}.

外圈剩余顶点un-5,…,un-1,un分别着色为b、c、a、c、a、b;里圈剩余顶点vn-5,…,vn-1,vn分别着色为a、a、b、b、b、c.因为顶点u1,u2,…,un-7,un-6用a、b、c循环着色,所以对顶点ui,2≤i≤n-7,有

φ({ui-1,ui,ui+1})={a,b,c},

从而|φ(NG(ui))|≥2.又因为

φ(u1)=a,φ(un)=b,

φ(u2)=b,φ(v1)=c,

所以

|φ(NG(u1))|=2.

同理可得

|φ(NG(ui))|=2,n-6≤i≤n.

由映射可得:

φ(vi-3)=φ(vi+3),φ(vi)≠φ(ui),

φ(ui)=φ(ui+3)=φ(ui-3).

因此,对任意vi∈{v4,v5,…,vn-9}有

φ({vi,vi-3,vi+3,ui})={a,b,c},

所以

|φ(NG(vi))|≥2.

又因为

φ(v1)=c,φ(vn-2)=b,

φ(v4)=b,φ(u1)=a,

所以

|φ(NG(v1))|=2.

同理可得

|φ(NG(vi))|=2, 2≤i≤3或者n-8≤i≤n.

因此,在这种情况下,φ是广义Petersen图Pn,t的一个(3,2)-着色.

综上所述,当n≠0(mod3),t=3时,Pn,t有一个(3,2)-着色.又因为χ2(Pn,t)≥3,即得

χ2(Pn,t)=3.

定理2得证.

由定理1知,当n≡0(mod3),t≡±1(mod3)时,证明χ2(Pn,t)=3.由定理2,当n≡0(mod3)时,证明当t=3时,χ2(Pn,t)=3.对于t=6,9,…的情况,本文没有完整刻画出来,但下面的定理说明当n≡0(mod3),t=6,9,…时的部分情况.

定理 3若n=mt,m≡0(mod3),t≡0(mod3),则χ2(Pn,t)=3.

证明因为(n,t)=t,则V={v1,v2,…,vn}导出的子图G[V]是t个不交的m阶圈.下面构造广义Petersen图Pn,t的一个(3,2)-着色φ.定义映射φ:V(Pn,t)→{a,b,c}如下：

φ-1(a)={vft+i|1≤i≤t,

f=0,3,6,…,m-3};

φ-1(b)={vft+i|1≤i≤t,

f=1,4,7,…,m-2};

φ-1(c)={vft+i|1≤i≤t,

f=2,5,8,…,m-1}.

外圈顶点uft+1,uft+2,…,uft+t,当f=0,3,6,…,m-3时,分别用b、c、b、c循环着色；当f=1,4,7,…,m-2时,分别用a、c、a、c循环着色；当f=2,5,8,…,m-1时,分别用b、a、b、a循环着色.

因为m≡0(mod3),t≡0(mod3),所以由映射可得

φ({vi-t,vi,vi+t})={a,b,c}.

因此

|φ(NG(vi))|≥2.

对于外圈顶点uft+2,…,uft+t-1,由着色过程可知

φ(uft+j)≠φ(vft+j),

φ(uft+t)≠φ(uft+t-1),

φ(uft+j+1)≠φ(uft+j),j=1,2,…,t-1,

所以对任意ui∈{uft+1,uft+2,…,uft+t},有

|φ(NG(ui))|≥2.

因此,φ是广义Petersen图Pn,t的一个(3,2)-着色.

综上所述,在这种情况下,χ2(Pn,t)≤3,又因为χ2(Pn,t)≥3,即得χ2(Pn,t)=3.定理得证.

由已知结论,知道广义Petersen图的2-hued着色数是3或4,本文接下来刻画2-hued着色数是4的广义Petersen图.

定理 4若n≠0(mod3),则χ2(Pn,1)=4.

证明广义Petersen图是3-正则图,且

χ2(Pn,t)≤4.

只需证

χ2(Pn,t)≥4.

下面证明,对于Pn,1找不到一个(3,2)-着色.设存在φ:V(Pn,1)→{a,b,c}是Pn,1的一个(3,2)-着色.由于对称性,不妨设

φ(u1)=a,φ(u2)=b.

情形1φ(v1)=c,则由(3,2)-着色的定义知

φ(v2)≠φ(v1)

且

φ(v2)≠φ(u2),

所以φ(v2)=a.进一步,因为

|φ(NG(u2))|≥2,

故φ(u3)=c.又因为

φ(v3)≠φ(v2)=a,

φ(v3)≠φ(u3)=c,

所以φ(v3)=b.按上述着色过程可得:

φ-1(a)={ui,vj|i≡1(mod3),j≡2(mod3)};

φ-1(b)={ui,vj|i≡2(mod3),j≡0(mod3)};

φ-1(c)={ui,vj|i≡0(mod3),j≡1(mod3)}.

具体着色如图1所示.当n≡1(mod3)时,有

图1 广义Petersen图Pn,1且φ(v1)=c

φ(un)=a,

而φ(u1)=a且u1un∈E(Pn,1),矛盾.当n≡2(mod3)时,有φ(vn)=a,而φ(v2)=a,φ(u1)=a,则|φ(NG(v1))|=1,矛盾.

情形2φ(v1)=b,则由

|φ(NG(u1))|≥2,

得

φ(un)=c.

因为φ(vn)≠φ(v1)且φ(vn)≠φ(un),则φ(vn)=a.按上述着色过程可得φ(un-1)=b,φ(vn-1)=c,….观察知,外圈顶点u2,u1,un,un-1,…,u4,u3按照b、a、c循环着色;里圈顶点v1,vn,vn-1,…,v3,v2按照b、a、c循环着色,具体着色如图2所示.当n≡1(mod3)时,有φ(u3)=b,而φ(u2)=b且u2u3∈E(Pn,1),矛盾.当n≡2(mod3)时,φ(v3)=b,φ(v1)=b,且φ(u2)=b,则|φ(NG(v2))|=1,矛盾.