一类特殊图的两种染色

李超，张东翰

（商洛学院数学与计算机应用学院，陕西商洛　726000）

数学研究

一类特殊图的两种染色

李超，张东翰

（商洛学院数学与计算机应用学院，陕西商洛726000）

利用穷举法和组合分析法讨论了一类特殊图的邻强边染色和邻点可区别的全染色，通过构造具体染色得到了该类图的邻强边色数和邻点可区别的全色数。

穷举法；邻强边染色；邻点可区别的全染色

图的染色是图论的主要研究内容之一，很多人对其进行了研究，文献［1］给出了图的邻强边染色的概念和一些特殊图的具体染色，文献［2-3］通过构造具体染色得到了一些特殊图的邻强边染色数，文献［4］给出了邻点可区别的全染色的概念和若干特殊图的染色，文献［5-6］给出了若干特殊图的邻点可区别的全色数。本文将研究一类特殊图的邻强边染色和邻点可区别的全染色。

1　预备知识

定义2［4-6］设G（V，E）是简单图，k是自然数，f是从V（G）∪E（G）到C=｛1，2，…，k｝的映射，如果满足：

如果f是一个k正常全染色，并且满足

定义3［7］由2个回路Cn恰有一个公共点所组成的图记作D2，n，

其中，点集V（D2，n）=｛v0，v1，…，vn-1，u1，u2，…，un-1｝，边集E（D2，n）=｛v0v1，v1v2，…，vn-1v0，v0u1，u1u2，…，un-1，un-2un-1，un-1v0｝

引理1［1-3］对于简单图G，有Δ≤χ′as（G）；若G有相邻的两个最大度点，则有Δ+1≤χ′as（G），其中Δ代表图G的最大度。

引理2［4-6］对于简单图G，有Δ+1≤χ′at（G）；若G有相邻的两个最大度点，则有Δ+2≤χ′at（G），其中Δ代表图G的最大度。

本文中未加叙述的术语、记号可在文献［8-10］中找到。

2　定理及其证明

定理1 对于图D2，n（n≥3），有χ′as（D2，n）=4。

证明 由于没有相邻的最大度点，所以根据引理1可知χ′as（D2，n）≥4，现给出一个4-ASEC，设色集合C=｛1，2，3，4｝。对于边v0v1，v1v2，v2v3，…，vn-2vn-1分别用色1，3，4循环染，对于边vn-1v0用色2染；对于边v0u1，u1u2，u2u3，…，un-2un-1分别用色3，1，2循环染，对于边un-1v0用色4染，则此染色法显然是一个4-ASEC，即χ′as（D2，n）=4。

定理2 对于图D2，n（n≥3），有χat（D2，n）=5。

证明 由于没有相邻的最大度点，所以根据引理2可知χat（D2，n）≥5，现给出一个5-AVDTC，设色集合C=｛1，2，3，4，5｝。对于边v0v1，v1v2，v2v3，…，vn-2vn-1分别用色1，5循环染，对于边vn-1v0用色2染；对于边v0u1，u1u2，u2u3，…，un-2un-1分别用色3，5循环染，对于边un-1用色4染。对于点v1，v2，v3…，vn-1分别用色3，4循环染，对于点v0用色5染；对于点u1，u2，u3，…，un-1分别用色1，2循环染，则该染色法显然是一个5-AVDTC，即χat（D2，n）=5。

［1］ZHANG Z F，LIU L Z，WANG J F.On the adjacent strong edge-coloring of Graphs［J］.Applied Math Letters，2002（15）：623-626.

［2］马少仙，马刚，张忠辅.Pm∨Fn的邻强边染色［J］.兰州大学学报（自然科学版），2008，44（1）：112-114.

［3］戴韵.图的邻强边染色［D］.金华：浙江师范大学，2006：11-17.

［4］张忠辅，陈祥恩，李敬文，等.关于图的邻点可区别的全染色［J］.中国科学：A辑，2004，35（5）：574-583.

［5］陈祥恩，张忠辅.Pm∨Fn的邻点可区别的全染色［J］.西北师范大学学报，2005，41（1）：13-15.

［6］闫丽红，王治文，张忠辅.广义θ-图的邻点可区别的全染色［J］.经济数学，2007，24（1）：103-106.

［7］徐荣贵，孔祥阳，徐保根.两类特殊图的控制数［J］.江西科学，2015，33（1）：57-58.

［8］张东翰.图Dn，4的邻点强可区别的全染色［J］.商洛学院学报，2014，28（6）：8-9.

［9］BONDYJA，MURTYUSR.GraphTheorywithApplications ［M］.New York：The Macmillan Press Ltd，1976：127-167.

［10］王晓，汪小黎.不含2K2为导出子图的图的染色［J］.商洛学院学报，2015，29（2）：3-4.

（责任编辑：李堆淑）

Two Colorings of A kind of Special Graph

LI Chao，ZHANG Dong-han
（College of Mathematics and Computer Applications，Shangluo University，Shangluo 726000，Shaanxi）

The adjacent strong edge coloring and the adjacent vertex distinguishing total coloring of a kind of special graph are discussed with the exhaustion method and the combination analytic method.The adjacent strong edge chromatic number and the adjacent vertex distinguishing total chromatic number of the graph are gained by construction of specific coloring.

the exhaustion method；adjacent strong edge coloring；adjacent vertex distinguishing total coloring

O157.5

A

1674-0033（2016）04-0001-02

10.13440/j.slxy.1674-0033.2016.04.001

2016-05-18

陕西省自然科学基础研究计划项目（2014JM2－1007）

李超，男，陕西镇安人，教授