关于图Pa,b的邻点可区别染色

严谦泰

(安阳师范学院 数学与统计学院，河南 安阳 455000)

1 研究背景

图的染色是图论的重要研究内容，由计算机科学和信息科学等所产生的一般点可区别边染色[1]、邻点可区别边染色[2-6]、邻点可区别全染色[7]、邻点强可区别全染色[8]等染色法，这些都是十分困难的问题，至今文献甚少。文中将通过具体的染色方法，给出图Pa,b的邻点可区别边染色数、邻点可区别全染色数、邻点强可区别全染色数。

定义2[7]图G(V,E)的一个正常全染色f:V∪E→{1,2,…,k}，如果满足：

1)对任意的uv∈E有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv);

2)对任意的uv,vw∈E有f(uv)≠f(vw)，且C(u)≠C(v)。

则称f是图G(V,E)的一个邻点可区别全染色，简记为k-AVETC。在k-AVDTC中最小的数k称为图G(V,E)的一个邻点可区别全染色数，记为χat(G)=min{k|k-AVDTC}。

定义3[8]设G(V,E)是阶数不小于3的简单连通图，f是从V(G)∪E(G)到{1,2,…,k}的映射，满足:

1) 对任意的边uv∈E(G)，f(u)≠f(v)，f(u)≠f(uv)，f(v)≠f(uv);

2)对任意的两相邻边uv，uw∈E(G)(v≠w)，f(uv)≠f(uw);

3)对任意的边uv∈E(G)，其端点的色集合满足C(u)≠C(v)，其中一顶点u的色集合

C(u)={f(u)}∪{f(v)|uv∈E(G)}

∪{f(uv)|uv∈E(G)}

则称f是图G的一个邻点强可区别的全染色，简记作k-AVSDTC，且称数

χast(G)={k|G所有的k-AVSDTC}

为G的邻点强可区别的全染色数。

定义4[9]设u,v是两个固定顶点，用b条内部互不相交且长度均为a的道路连接u,v的图用Pa,b表示。

本文涉及的图都是简单连通有限图，未加说明的术语与记号见文献[10]。

2 主要结论及其证明

引理2[7]如果简单图G是阶不小于3的图，则χat(G)≥Δ(G)+1；如果简单图G有两个相邻的最大度顶点，则χat(G)≥Δ(G)+2。

引理3[8]如果简单图G是阶不小于3的图，则χast(G)≥Δ(G)+1;而G中至少有最大度顶点相邻，则有χast(G)≥Δ(G)+2。

引理4[8]对于n阶路Pn(n≥3)，有

χast(Pn)={4,n≡0(mod 2)

5,n≡1(mod 2)

……

即第1条路上的边用1,2,…,b循环染色；第2条路上的边用2,3,…,b，1循环染色；第3条路上的边用3,4,…,b，1，2循环染色；……；第b条路上的边用b，1,2,…,b-1循环染色。这是Pa,b的一个b-AVDEC。

定理2 对于图Pa,b(a≥3,b≥3)，有χat(Pa,b)=b+1。

证明 情形1 对于图Pa,3(a≥3)，有χat(Pa,3)=4。

由于Δ(Pa,3)=3，由引理2知，χat(Pa,b)≥4，下证χat(Pa,b)=4。Pa,3中每条路上一共有2a+1个顶点和边。

故f是Pa,3的4-AVDTC。

故f是Pa,3的4-AVDTC。

综上可知，χat(Pa,3)=4。

情形2 对于图Pa,b(a≥3,b≥4)，由于Δ(Pa,b)=b，故χat(Pa,b)≥b+1，下证χat(Pa,b)=b+1。Pa,b(a≥3,b≥3)中每条路上一共有2a+1个顶点和边。

第1条路上前2a个顶点和边用1,2,…,b,b+1循环染色；

第2条路上的顶点和边用1，3，4，…，b+1，2循环染色；

第3条路上的顶点和边用1，4，5，…，b+1，2，3循环染色；

……

第b条路上的顶点和边用1,b+1,2,3,…,b循环染色。

这是Pa,b的一个(b+1)-AVDTC。

……

这是Pa,b的一个(b+1)-AVDTC。

……

这是Pa,b的一个(b+1)-AVDTC。

一般地，当2a+1≡i(mod(b+1))时，

……

……

综上可知，f是Pa,b的一个(b+1)-AVDTC。

定理3 对于图Pa,3(a≥4)，有

χast(Pa,3)={4,a≡0(mod 2)

5,a≡1(mod 2)

情形1.1 当a≡0(mod 3)时，此时2a是3的倍数。

当i≡1(mod 2)时：

当i≡1(mod 2)时：

当i≡1(mod 2)时：

这是Pa,3(a≥4)的一个4-AVSDTC。

情形1.2 当a≡1(mod 3)时。

当i≡1(mod 2)时：

当i≡1(mod 2)时：

当i≡1(mod 2)时：

这是Pa,3(a≥4)的一个4-AVSDTC。

情形1.3 当a≡2(mod 3)时。

当i≡1(mod 2)时：

当i≡1(mod 2)时：

当i≡1(mod 2)时：

这是Pa,3(a≥4)的一个4-AVSDTC。

情形2.1 当a≡0(mod 5)时，

这是Pa,3(a≥4)的一个5-AVSDTC。

情形2.2 当a≡1(mod 5)时，

这是Pa,3(a≥4)的一个5-AVSDTC。

情形2.3 当a≡2(mod 5)时，

这是Pa,3(a≥4)的一个5-AVSDTC。

情形2.4 当a≡3(mod 5)时，

这是Pa,3(a≥4)的一个5-AVSDTC。

情形2.5 当a≡4(mod 5)时，

这是Pa,3(a≥4)的一个5-AVSDTC。

综上可知，χast(Pa,3)={4,a≡0(mod 2)

5,a≡1(mod 2)。

定理4 对于图Pa,b(a≥4,b≥4)，有χast(Pa,b)=b+1。

情形1 当a≡0(mod 5)时。

第i条路上的顶点用1(i+1)(i+2)(i+3)(i+4)循环染色，i=1,2,…,b，其中i+1，i+2，i+3，i+4(≥b+2)是在模b(modb)的意义下。 第i条路上的边用(i+2)(i+3)(i+4)1(i+1)循环染色。同定理3可验证f是Pa,b(a≥4,b≥4)的一个(b+1)-AVSDTC。

情形2 当a≡1(mod 5)时。

情形3 当a≡2(mod 5)时。

第i条路上的顶点用1(i+1)(i+2)(i+3)(i+4)循环染色，i=1,2,…,b，其中i+1，i+2，i+3，i+4(≥b+2)是在b(modb)模的意义下。 第i条路上的边用(i+2)(i+3)(i+4)1(i+1)循环染色。可验证f是Pa,b(a≥4,b≥4)的一个(b+1)-AVSDTC。。

情形4 当a≡3(mod 5)时。

情形5 当a≡4(mod 5)时。

综上可知，对图Pa,b(a≥4,b≥4)，有χast(Pa,b)=b+1。