一類特殊圖的兩種染色

李超，張東翰

（商洛學(xué)院數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院，陜西商洛　726000）

數(shù)學(xué)研究

一類特殊圖的兩種染色

李超，張東翰

（商洛學(xué)院數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院，陜西商洛726000）

利用窮舉法和組合分析法討論了一類特殊圖的鄰強(qiáng)邊染色和鄰點(diǎn)可區(qū)別的全染色，通過構(gòu)造具體染色得到了該類圖的鄰強(qiáng)邊色數(shù)和鄰點(diǎn)可區(qū)別的全色數(shù)。

窮舉法；鄰強(qiáng)邊染色；鄰點(diǎn)可區(qū)別的全染色

圖的染色是圖論的主要研究內(nèi)容之一，很多人對(duì)其進(jìn)行了研究，文獻(xiàn)［1］給出了圖的鄰強(qiáng)邊染色的概念和一些特殊圖的具體染色，文獻(xiàn)［2-3］通過構(gòu)造具體染色得到了一些特殊圖的鄰強(qiáng)邊染色數(shù)，文獻(xiàn)［4］給出了鄰點(diǎn)可區(qū)別的全染色的概念和若干特殊圖的染色，文獻(xiàn)［5-6］給出了若干特殊圖的鄰點(diǎn)可區(qū)別的全色數(shù)。本文將研究一類特殊圖的鄰強(qiáng)邊染色和鄰點(diǎn)可區(qū)別的全染色。

1　預(yù)備知識(shí)

定義2［4-6］設(shè)G（V，E）是簡單圖，k是自然數(shù)，f是從V（G）∪E（G）到C=｛1，2，…，k｝的映射，如果滿足：

如果f是一個(gè)k正常全染色，并且滿足

定義3［7］由2個(gè)回路Cn恰有一個(gè)公共點(diǎn)所組成的圖記作D2，n，

其中，點(diǎ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］對(duì)于簡單圖G，有Δ≤χ′as（G）；若G有相鄰的兩個(gè)最大度點(diǎn)，則有Δ+1≤χ′as（G），其中Δ代表圖G的最大度。

引理2［4-6］對(duì)于簡單圖G，有Δ+1≤χ′at（G）；若G有相鄰的兩個(gè)最大度點(diǎn)，則有Δ+2≤χ′at（G），其中Δ代表圖G的最大度。

本文中未加敘述的術(shù)語、記號(hào)可在文獻(xiàn)［8-10］中找到。

2　定理及其證明

定理1 對(duì)于圖D2，n（n≥3），有χ′as（D2，n）=4。

證明 由于沒有相鄰的最大度點(diǎn)，所以根據(jù)引理1可知χ′as（D2，n）≥4，現(xiàn)給出一個(gè)4-ASEC，設(shè)色集合C=｛1，2，3，4｝。對(duì)于邊v0v1，v1v2，v2v3，…，vn-2vn-1分別用色1，3，4循環(huán)染，對(duì)于邊vn-1v0用色2染；對(duì)于邊v0u1，u1u2，u2u3，…，un-2un-1分別用色3，1，2循環(huán)染，對(duì)于邊un-1v0用色4染，則此染色法顯然是一個(gè)4-ASEC，即χ′as（D2，n）=4。

定理2 對(duì)于圖D2，n（n≥3），有χat（D2，n）=5。

證明 由于沒有相鄰的最大度點(diǎn)，所以根據(jù)引理2可知χat（D2，n）≥5，現(xiàn)給出一個(gè)5-AVDTC，設(shè)色集合C=｛1，2，3，4，5｝。對(duì)于邊v0v1，v1v2，v2v3，…，vn-2vn-1分別用色1，5循環(huán)染，對(duì)于邊vn-1v0用色2染；對(duì)于邊v0u1，u1u2，u2u3，…，un-2un-1分別用色3，5循環(huán)染，對(duì)于邊un-1用色4染。對(duì)于點(diǎn)v1，v2，v3…，vn-1分別用色3，4循環(huán)染，對(duì)于點(diǎn)v0用色5染；對(duì)于點(diǎn)u1，u2，u3，…，un-1分別用色1，2循環(huán)染，則該染色法顯然是一個(gè)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的鄰強(qiáng)邊染色［J］.蘭州大學(xué)學(xué)報(bào)（自然科學(xué)版），2008，44（1）：112-114.

［3］戴韻.圖的鄰強(qiáng)邊染色［D］.金華：浙江師范大學(xué)，2006：11-17.

［4］張忠輔，陳祥恩，李敬文，等.關(guān)于圖的鄰點(diǎn)可區(qū)別的全染色［J］.中國科學(xué)：A輯，2004，35（5）：574-583.

［5］陳祥恩，張忠輔.Pm∨Fn的鄰點(diǎn)可區(qū)別的全染色［J］.西北師范大學(xué)學(xué)報(bào)，2005，41（1）：13-15.

［6］閆麗紅，王治文，張忠輔.廣義θ-圖的鄰點(diǎn)可區(qū)別的全染色［J］.經(jīng)濟(jì)數(shù)學(xué)，2007，24（1）：103-106.

［7］徐榮貴，孔祥陽，徐保根.兩類特殊圖的控制數(shù)［J］.江西科學(xué)，2015，33（1）：57-58.

［8］張東翰.圖Dn，4的鄰點(diǎn)強(qiáng)可區(qū)別的全染色［J］.商洛學(xué)院學(xué)報(bào)，2014，28（6）：8-9.

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

［10］王曉，汪小黎.不含2K2為導(dǎo)出子圖的圖的染色［J］.商洛學(xué)院學(xué)報(bào)，2015，29（2）：3-4.

（責(zé)任編輯：李堆淑）

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

陜西省自然科學(xué)基礎(chǔ)研究計(jì)劃項(xiàng)目（2014JM2－1007）

李超，男，陜西鎮(zhèn)安人，教授