Fm、Pn⊙Fm和Cn⊙Fm的r-hued染色研究

西日尼阿依·努尔麦麦提, 刘凤霞

(1. 喀什大学 数学与统计学院, 新疆 喀什 844000; 2. 新疆大学 数学与系统科学学院, 新疆 乌鲁木齐 830046)

图的r-hued染色的概念首次由Montgomery等[1]提出,并在文献[2]中得出了特殊情形r=2的一些结果.在早期阶段,2-hued染色被称为dynamic染色.文献[3]首次研究了关于r的一般值的r-hued染色,并且r-hued染色被称为条件染色.在后来的研究中,专业名称还没统一,但大多数研究者都在使用“r-hued染色”或者“r-dynamic染色”.

(C1) 若uv∈E(G),则c(u)≠c(v);

(C2) 对于任意v∈V(G),则

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

引理 1[3]χ(G)=χ1(G)≤χ2(G)≤…≤χΔ(G)(G)=χΔ(G)+1(G)=…=χ(G2),如果r≥Δ(G),那么χr(G)=χΔ(G)(G).

图G的平方图记为G2,表示满足V(G2)=V(G),uv∈E(G2),当且仅当点u、v在图G中的距离最多是2的图.

引理 2[3]设G是一个图,则有χr(G)≥min{Δ(G),r}+1,其中r≥1.

图G和图H的corona乘积图记为G⊙H,是将图G拷贝一份、图H拷贝|V(G)|份,把图G的第i个顶点跟图H的第i(1≤i≤|V(G)|)个拷贝份的每个顶点连边而得到的图.关于2个图的corona乘积图的r-hued染色数的研究早期已有很多结果,比如:在2017年,Kristiana等[5]刻画了路与路、路与圈、路与轮图的corona乘积图的r-hued染色数;在2018年,Kristiana等[6]刻画了星图和轮图、轮图和轮图的corona乘积图的r-hued染色数,Kristiana等[7]刻画了星图与完全图、完全图与完全图的corona乘积图的r-hued染色数等.

本文主要研究Fm、Pn⊙Fm和Cn⊙Fm的r-hued染色数.

1 Fm的r-hued染色数

本节主要研究扇图Fm的r-hued染色数,先给出本文的结论.

定理 1设Fm是一个扇图,m≥2,则

证明扇图Fm是顶点集合为

V(Fm)={u0,u1,u2,…,um},边集合为

E(Fm)={u0ui|1≤i≤m}∪

{uiui+1|1≤i≤m-1}

的连通图,其顶点个数为

|V(Fm)|=m+1,边的个数为

|E(Fm)|=2m-1,且Δ(Fm)=m,d(u0)=m,d(u1)=d(um)=2,当2≤i≤m-1时,d(ui)=3.

为了刻画Fm的r-hued染色数的精确值,根据r的取值范围,分以下3种情形进行讨论.

情形 1 1≤r≤2.定义映射c1:V(Fm)→{0,1,2}如下:

c1(u0)=0,

其中,m≥2.

当r=2时,对于ui而言,满足

2=|c1(N(u0))|≥min{d(u0),2}=2;

当i=1,m时,

2=|c1(N(ui))|≥min{d(ui),2}=2;

当i=2≤i≤m-1时,

2=|c1(N(ui))|≥min{d(ui),2}=2.

从而c1是图Fm的一个(3,2)-染色,即χ2(Fm)≤3.由引理2知

χ2(Fm)≥min{Δ(Fm),2}+1=

min{m,2}+1=3,从而χ2(Fm)=3.

因为Fm中包含三角形,有χ1(Fm)≥3.由引理1,χ1(Fm)≤χ2(Fm)≤3,所以χ1(Fm)=3,故

χ1≤r≤2(Fm)=3.

情形 2 3≤r≤Δ.定义映射c2:V(Fm)→{0,1,2,…,r}如下:

c2(u0)=0,

其中,m=Δ≥3.

r=|c2(N(u0))|≥min{d(u0),r}={m,r}=r;

当i=1,m时,

2=|c2(N(ui))|≥min{d(ui),2}={2,r}=2;

当1

3=|c2(N(ui))|≥min{d(ui),r}={3,r}=3.

从而c2是图Fm的一个(r+1,r)-染色,即χr(Fm)≤r+1.由引理2知,χr(Fm)≥min{Δ(Fm),r}+1=min{m,r}+1=r+1,从而χr(Fm)=r+1,故

χ3≤r≤Δ(Fm)=r+1.

情形 3r>Δ.定义映射c3:V(Fm)→{0,1,2,…,m}如下:

c3(u0)=0,c3(ui)=i, 1≤i≤m,其中,m≥3.

当i=1,m时,

2=|c3(N(ui))|≥min{2,r}=2,当1

3=|c3(N(ui))|≥min{3,r}=3,

m=|c3(N(u0))|≥min{Δ,r}=Δ=m.

从而c3是图Fm的一个(m+1,r)-染色,即

χr(Fm)≤m+1.

由引理2知

χr(Fm)≥min{Δ(Fm),r}+1=

min{m,r}+1≥m+1,从而χr>Δ(Fm)=m+1.

2 Pn⊙Fm的r-hued染色数

本节主要研究路Pn和扇图Fm的corona乘积图的r-hued染色数.

定理 2设Pn⊙Fm是路和扇图的corona乘积图,n≥2,m≥2,则

证明路的顶点集合为

V1(Pn)={v1,v2,…,vn},边集合为

E1(Pn)={vivi+1|1≤i≤n-1};

扇图的顶点集合为

V2(Fm)={u0,u1,u2,…,um},边集合为

E2(Fm)={u0uj|1≤j≤m}∪

{ujuj+1|1≤j≤m-1}.

由此,可以假设Pn⊙Fm的顶点集合为

V(Pn⊙Fm)={vi|1≤i≤n}∪

{uij|1≤i≤n,0≤j≤m},即

|V(Pn⊙Fm)|=n(m+2),边集合为

E(Pn⊙Fm)={vivi+1|1≤i≤n-1}∪

{viuij|1≤i≤n,0≤j≤m}∪

{ui0uij|1≤i≤n,1≤j≤m}∪

{uijui(j+1)|1≤i≤n,1≤j≤m-1},则|E(Pn⊙Fm)|=3mn+n-1,且当n=2时,Δ(Pn⊙Fm)=m+2;当n≥3时,Δ(Pn⊙Fm)=m+3.P4与F5的corona乘积图如图1所示.

图 1 P4与F5的corona乘积图

为了刻画Pn⊙Fm的r-hued染色数的精确值,根据r的取值范围,分以下3种情形进行讨论.

情形 1 1≤r≤3.定义映射c4:V(Pn⊙Fm)→{1,2,3,4}如下:

其中,n≥2,m≥2.

映射c4是图Pn⊙Fm的一个(4,3)-染色,即χ3(Pn⊙Fm)≤4.由引理2知χr(Pn⊙Fm)≥min{Δ(Pn⊙Fm),3}+1=min{m+3,3}+1=4,从而χ3(Pn⊙Fm)=4.

因为Pn⊙Fm中包含K4,所以χ1(Pn⊙Fm)≥4.由引理1知χ1(Pn⊙Fm)≤χ3(Pn⊙Fm)=4,从而χ1(Pn⊙Fm)=4,而

4=χ1(Pn⊙Fm)≤χ2(Pn⊙Fm)≤χ3(Pn⊙Fm)=4,即χ2(Pn⊙Fm)=4,故χ1≤r≤3(Pn⊙Fm)=4.

情形 2 4≤r≤Δ-1.

子情形 2.1 4≤r≤Δ-2.定义映射

c51:V(Pn⊙Fm)→{1,2,…,r,r+1}

如下:

其中,n≥2,m≥3.

映射c51是图Pn⊙Fm的一个(r+1,r)-染色,即

χr(Pn⊙Fm)≤r+1.

子情形 2.2r=Δ-1.定义映射

c52:V(Pn⊙Fm)→{1,2,…,r,r+1}

如下:

其中,n≥2,m=r-2≥3.

映射c52是图Pn⊙Fm的一个(r+1,r)-染色,即

χr(Pn⊙Fm)≤r+1.

由子情形2.1和2.2可得,当4≤r≤Δ-1时,χr(Pn⊙Fm)≤r+1.由引理2知χr(Pn⊙Fm)≥min{Δ(Pn⊙Fm),r}+1=min{m+3,r}+1=r+1,从而χr(Pn⊙Fm)=r+1,故

χ4≤r≤Δ-1(Pn⊙Fm)=r+1.

情形 3r≥Δ.定义映射

c6:V(Pn⊙Fm)→{1,2,…,Δ,Δ+1}

如下.

子情形 3.1 当n=2,m≥3时,

c6(v1)=1,c6(v2)=2,

映射c6是图Pn⊙Fm的一个(m+3,r)-染色,即

χr(Pn⊙Fm)≤m+3=Δ+1.

子情形 3.2 当n≥3,m≥3时,

映射c6是图Pn⊙Fm的一个(m+4,r)-染色,即

χr(Pn⊙Fm)≤m+4=Δ+1.

由子情形3.1和3.2可得χr(Pn⊙Fm)≤Δ+1.由引理2知χr(Pn⊙Fm)≥min{Δ(Pn⊙Fm),r}+1=min{Δ,r}+1=Δ+1,从而χr(Pn⊙Fm)=Δ+1,故

χr≥Δ(Pn⊙Fm)=Δ+1.

例 1设Pn⊙Fm是路和扇图的corona乘积图,讨论n=2或3,m=2,r=4的情形:

1) 当n=2,m=2时,此图的最大度为4且c(v1)=1,c(v2)=5,c(ui0)=2,c(ui1)=3,c(ui2)=4(i=1,2),即χr=4(Pn⊙Fm)=5.

2) 当n=3,m=2时,此图的最大度为5且c(v1)=1,c(v2)=5,c(v3)=1,c(ui0)=2,c(ui1)=3,c(ui2)=4(i=1,2,3),即χr=4(Pn⊙Fm)=r+1=5.

3 Cn⊙Fm的r-hued染色数

本节主要研究圈Cn和扇图Fm的corona乘积图的r-hued染色数.

定理 3设Cn⊙Fm是圈和扇图的corona乘积图,n≥3,m≥3,则

证明圈的顶点集合为

V1(Cn)={v1,v2,…,vn},边集合记为

E1(Cn)={vivi+1|1≤i≤n-1}∪{v1vn};

扇图的顶点集合为

V2(Fm)={u0,u1,u2,…,um},边集合为

E2(Fm)={u0uj|1≤j≤m}∪{ujuj+1|1≤j≤m-1}.

由此,可以假设Cn⊙Fm的顶点集合为

V(Cn⊙Fm)={vi|1≤i≤n}∪{uij|1≤i≤n,0≤j≤m},即

|V(Cn⊙Fm)|=n(m+2),边集合为

E(Cn⊙Fm)={vivi+1|1≤i≤n-1}∪{v1vn}∪

{viuij|1≤i≤n,0≤j≤m}∪{ui0uij|1≤i≤n,1≤j≤m}∪

{uijui(j+1)|1≤i≤n,1≤j≤m-1},则

|E(Cn⊙Fm)|=3mn+n,且Δ(Cn⊙Fm)=m+3.

为了刻画Cn⊙Fm的r-hued染色数的精确值,根据r的取值范围,分以下3种情形进行讨论.

情形 1 1≤r≤3.

子情形 1.1 设n是偶数且n≥4,定义映射c71:V(Cn⊙Fm)→{1,2,3,4}如下:

映射c71是图Cn⊙Fm的一个(4,3)-染色,即

χ3(Cn⊙Fm)≤4.

子情形 1.2 设n是奇数且n≥3,定义

c72:V(Cn⊙Fm)→{1,2,3,4}

如下:

映射c72是图Cn⊙Fm的一个(4,3)-染色,即

χ3(Cn⊙Fm)≤4.

由子情形1.1和1.2可得χ3(Cn⊙Fm)≤4.由引理2知χ3(Cn⊙Fm)≥min{Δ(Cn⊙Fm),3}+1=min{m+3,3}+1=4,从而χ3(Cn⊙Fm)=4.

因为Cn⊙Fm中包含K4,所以χ1(Cn⊙Fm)≥4.由引理1知χ1(Cn⊙Fm)≤χ3(Cn⊙Fm)=4,从而χ1(Cn⊙Fm)=4,而

4=χ1(Cn⊙Fm)≤χ2(Cn⊙Fm)≤

χ3(Cn⊙Fm)=4,即χ2(Cn⊙Fm)=4,故χ1≤r≤3(Cn⊙Fm)=4.

情形 2 4≤r≤Δ-1.

子情形 2.1 4≤r≤Δ-2,n是偶数.定义映射c81:V(Cn⊙Fm)→{1,2,…,r,r+1}如下:

其中,n≥4.

映射c81是图Cn⊙Fm的一个(r+1,r)-染色,即

χr(Cn⊙Fm)≤r+1.

子情形 2.2 4≤r≤Δ-2,n是奇数.定义映射c82:V(Cn⊙Fm)→{1,2,…,r,r+1}如下:

其中,n≥3.

映射c82是图Cn⊙Fm的一个(r+1,r)-染色,即

χr(Cn⊙Fm)≤r+1.

子情形 2.3r=Δ-1,n是偶数.定义映射c83:V(Cn⊙Fm)→{1,2,…,r,r+1}如下:

其中,n≥4,m=r-2≥3.

映射c83是图Cn⊙Fm的一个(r+1,r)-染色,即

χr(Cn⊙Fm)≤r+1.

子情形 2.4r=Δ-1,n是奇数.定义映射c84:V(Cn⊙Fm)→{1,2,…,r,r+1}如下:

其中,n≥3,m=r-2≥3.

映射c84是图Cn⊙Fm的一个(r+1,r)-染色,即

χr(Cn⊙Fm)≤r+1.

由子情形2.1～2.4可得,当4≤r≤Δ-1时,χr(Cn⊙Fm)≤r+1.由引理2知χr(Cn⊙Fm)≥min{Δ(Cn⊙Fm),r}+1=min{m+3,r}+1=r+1,从而χr(Cn⊙Fm)=r+1,故

χ4≤r≤Δ-1(Cn⊙Fm)=r+1.

情形 3r≥Δ.

子情形 3.1 当n≡0(mod 3)时,定义映射c91:V(Cn⊙Fm)→{1,2,…,m+3,m+4}如下:

其中,m≥3.

映射c91是图Cn⊙Fm的一个(m+4,r)-染色,即

χr(Cn⊙Fm)≤m+4.

子情形 3.2 当n≡1(mod 3)时,定义映射c92:V(Cn⊙Fm)→{1,2,…,m+3,m+4}如下:

其中,m≥3.

映射c92是图Cn⊙Fm的一个(m+4,r)-染色,即χr(Cn⊙Fm)≤m+4.

子情形 3.3 当n≡2(mod 3)时,定义映射c93:V(Cn⊙Fm)→{1,2,…,m+3,m+4}如下:

其中,m≥3.

映射c93是图Cn⊙Fm的一个(m+4,r)-染色,即χr(Cn⊙Fm)≤m+4.

由子情形3.1～3.3可得,当r≥Δ时,

χr(Cn⊙Fm)≤m+4.

由引理2知χr(Cn⊙Fm)≥min{Δ(Cn⊙Fm),r}+1=min{m+3,r}+1=m+4,从而χr(Cn⊙Fm)=m+4,故χr≥Δ(Cn⊙Fm)=m+4.