路和圈幂图的邻点可区别E-全染色

董秀芳

(江苏省联合职业技术学院连云港财经分院 数学与应用数学系，江苏 连云港222003)

1 基本概念与引理

假定所讨论的图G(V，E)都是有限、无向简单连通图. 设Δ(G)和δ(G)分别表示图G 的最大度和最小度，T(G)是图的顶点和边组成集合. 令dG(u，v)表示G 中u，v2 个顶点最短路径的长度，若期间没有路径，令其为dG(u，v)∶=∞，明确图类的情况下，简记为d(u，v).令［k］={1，2，…，k}为k-色集(k 是正整数)，C(u)=表示顶点u 及其所有邻边的染色集合. 其他相关概念和术语请参看文献［1］.

图染色问题是图论中的一个重要研究方向，为了解决计算机科学、信号处理等领域中遇到的问题，许多图论专家相继提出了图的染色概念，如点可区别的边染色［2－3］，邻点可区别的边染色［4－5］，点可区别的全染色［6］，邻点可区别的全染色［7］等;2008 年张忠辅［8］等人又提出了图的邻点可区别E-全染色的概念，李沐春、王治文、王继顺［9－12］等研究了一些图的邻点可区别E-全染色. 确定图的邻点可区别E-全色数同样是NP-难问题.

定义1［8］对简单连通图G(V，E)和正整数k，f 是T(G)到［k］={1，2，…，k}的一个映射，如果f 满足

则称f 为一个图G 的邻点可区别E-全染色，简记为G 的k-AVDETC，并称

为G 的邻点可区别E-全色数.

猜想1［8］对简单图G(Δ(G)≥4)，且G≠Kn，G≠C2n+1，则

定义2［13］对图G(V，E)，若V(Gk)=V(G)，E(Gk)=E(G)∪{uv|d(u，v)=k}，称Gk为图G 的k-幂图. 如路的2-幂图P26，如图1 所示.

马生全，李敬文［13］等研究了Pkn(k≡2(mod 3))的邻点可区别的强全染色，王继顺［14］获得了Pkn(k≡2(mod 3))的D(2)-点可区别全色数，谷玉盈，王淑栋［15］确立了一些幂图的邻点可区别全色数.笔者研究了的邻点可区别E-全染色，通过给出其邻点可区别E-全色数说明猜想1 对于这类图是正确的.

图1 路P6 及其2-幂图（记作

2 主要结果与证明

引理1［1－2］对任意的简单图G，有χ(G)≤Δ(G)+1，等号成立当且仅当G 为奇圈或完全图.

引理2［8］对任意的简单图G，有χ(G)≤χeat(G)≤χ(G)+1.

引理3［8］对任意的简单图G 和H，有

其中，G∨H 为G 和H 的联图.

引理4［8］设Cn为n 阶圈，则

引理5［18］设Kn为n 阶完全图(n≥4)，则χeat(Kn)=n.

引理6 假定G 由m 个分支G1，G2，…，Gm组成，则有

证明 由定义1 易证结论成立.

定理1 设Pn是n(n≥2)阶路，则

证明 假定Pn=v1v2v3…vn，由于P2n包含子图K3，按照引理5 和引理6，有为证明结论成立，仅需证明P2n存在一个4-AVDETC.下面构造T(P2n)到［4］的染色法f 如下

按照该染色法f，易得当i≡1(mod 3)时，C(vi)={1，4}，当i≡2(mod 3)时，C(vi)={2，4}，当i≡0(mod 3)时，C(vi)={3，4}.

对任意相邻的顶点u，v P2n，由于C(u)≠C(v)，所以f 是P2n的一个4-AVDETC.

定理2 对n(n≥2)阶路Pn的k-幂图Pkn(n≥2k+2，k≥2)，有

证明 假定Pn=v1v2v3…vn，由于包含子图Ck+1，按照引理4 和引理6，当k 是奇数时当k 是偶数时为证明结论成立，仅需证明当k≡1(mod 2)时，Pkn存在一个3-AVDETC，当k≡0(mod 2)时，Pkn 存在一个4-AVDETC. 为此分2 种情况讨论如下

情形1 当k≡1(mod 2)时，构造T(Pkn)到［3］的染色法f 如下

下面验证该染色法f 满足定义1

易见f 是Pkn(k≡1(mod 2))的一个3-AVDETC. 事实上，一方面对任意相邻顶点vi，vi+1，，有C(vi)≠C(vi+1);另一方面，对任意顶点vi，由于i 和i+k 总是奇偶性相反，所以C(vi)≠C(vi+k). 从而(k≡1(mod 2)).

情形2 当k≡0(mod 2)时，按照如下的2 种情况定义从T(Pkn)到［4］的一个全染色法f

1)当k≡0(mod 2)，且k≠0，2(mod 10)时，令f

下面验证上述的染色法f 满足定义1

当k≠0，2(mod 10)时，由于k 是偶数，i +k 与i 的模不会相同，所以C(vi)≠C(vi+k)且C(vi)≠C(vi+1).故f 是Pkn的一个4-AVDETC，结论成立.

2)当k≡0(mod 2)，且k≡0，2(mod 10)时，构造f

对此染色法f，易得

所以，f 是Pkn(k≡0(mod 2))的一个4-AVDETC，结论成立.

定理3 令Cn为n(n≥3)阶圈，则有

证明 令Cn=v1v2v3…vnv1.下面分3 种情况讨论.

易见f 是C2n的一个4-AVDETC. 事实上，C2n所有相邻的顶点染色集是不同的，当i≡1(mod 3)时，C(vi)={1，4}，当i≡2(mod 3)时，C(vi)={2，4}，当i≡0(mod 3)时，C(vi)={3，4}.所以(n≡0(mod 2)).

情形2 当n≡1(mod 3)时，因为C2n包含子图K3，所以按照引理5 和引理现只要构造C2n的一个4-AVDETC 染色法f

则有

易见f 是C2n(n≡1(mod 2))的一个4-AVDETC . 故而结论成立.

情形3 当n≡2(mod 3)时，由于C2n包含子图K3，则由引理5 和引理6 有运用反证法说明C2n的4-不可染. 若用4 种颜色可得C2n的一个4-AVDETC，不妨先从i=1 用色1，2，3 分别染K3的顶点(vi，vi+1，vi+2)，依次循环染到第(n－2)/3 个K3. 至此还有vn－1，vn没有染. 现已不能用色1，2，3 染顶点vn－1，因为其相邻顶点v1，vn－2，vn－3已经分别用过1，2，3(如图2 所示). 所以只能用色4 染vn－1.再看vn，因为vn与顶点v1，v2，vn－2，vn－1都相邻，已经分别用1，2，3，4 分别染色，所以从1 到4 的4 种色不能满足得到一个4-AVDETC 的条件(如图3 所示)，否则与定义1 矛盾. 故只能用第五种色来染vn不妨令其为5. 由上述的讨论，C2n需要5 色才能满足5-AVDETC 的条件，下面给出C2n的一个5-AVDETC.

图2 vn-1 的邻点

图3 vn 的邻点

该染色法f 满足定义1

显然，f 是C2n的一个5-AVDETC. 从而结论成立.

［1］BONDY J A，MURTY U S R. Graph Theory［M］.New York:Springer，2008.

［2］BURRIS A C，SCHELP R H. Vertex-distinguishing proper edge-colorings［J］. Graph Theory，1997，26(2):73 －82.

［3］BAZGAN C，HARKAT-BENHAMDINE A，LI Hao，et al. On the vertex-distinguishing proper edge-colorings of graphs［J］. J.Combin. Theory Ser. B，1999，75(2):288 －301.

［4］ZHANG Zhongfu，LIU Linzhong，WANG Jianfang. Adjacent strong edge coloring of graph［J］.Applied Mathematics Letters，2002，15(5):623 －626.

［5］张忠辅，李敬文，陈祥恩，等.图的距离不大于β 的任意两点可区别边染色［J］. 数学学报，2006，49(3):703 －708.

［6］ZHANG Zhongfu，QIU Pengxiang，XU Baogen，et al. Vertex-distinguishing total coloring of graphs［J］. ArsCombinatoria，2008，87:33 －45.

［7］ZHANG Zhongfu，CHEN Xiangen，LI Jing-wen，et al. On adjacent-vertex-distinguishing total coloring of graphs［J］. Science ChinaSeries A:Mathematics，2005，48(3):289 －299.

［8］ZHANG Zhongfu，DOUGLAS R W，YAO Bing，et al. Edge adjacent vertex-distinguishing total coloring of graphs［EB/OL］.(2008 －06 －12)［2014 －02 －10］.http://202.201.18.40:8080/mas5/.

［9］李沐春，张忠辅.若干笛卡尔积图的邻点可区别E-全染色［J］.数学的实践与认识，2009，39(3):215 －219.

［10］周登杰，李沐春. 路和圈多重联图的邻点可区别E-全染色［J］. 纯粹数学与应用数学，2010，26(6):909 －914.

［11］王治文，张威，李沐春，等. 圈的多重联图的邻点可区别E-全染色的一些结果［J］.数学的实践与认识，2010，40(20):177 －180.

［12］WANG Jishun. Adjacent vertex-distinguishing E-total coloring on some join graphs Cm∨Gn［J］.Chinese Quarterly Journal of Mathematics，2012，27(3):328 －336.

［13］马生全，李敬文，马明，等.Pkn(k≡2(mod 3))的邻点可区别的强全染色［J］. 经济数学，2003(4):77 －80.

［14］王继顺.Pkn(k≡2(mod 3))的D(2)-点可区别全染色［J］. 数学的实践与认识，2011，41(2):190 －194.

［15］谷玉盈，王淑栋.幂图的邻点可区别全色数［J］.黑龙江大学学报:自然科学版，2008，25(2):193 －195.