一类特殊图的两种染色

李超，张东翰

（商洛学院数学与计算机应用学院，陕西商洛　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。……