K4-minor-free圖的鄰點(diǎn)可區(qū)別全染色

史小藝，張寧，萬(wàn)慧敏

（中國(guó)礦業(yè)大學(xué) 理學(xué)院，江蘇 徐州 221008）

K4-minor-free圖的鄰點(diǎn)可區(qū)別全染色

史小藝，張寧，萬(wàn)慧敏

（中國(guó)礦業(yè)大學(xué) 理學(xué)院，江蘇 徐州 221008）

圖G的一個(gè)正常全染色被稱為鄰點(diǎn)可區(qū)別全染色，如果G中任意兩個(gè)相鄰點(diǎn)的色集合不同.論文確定了 k4-minor-free圖的鄰點(diǎn)可區(qū)別全色數(shù).

全染色；鄰點(diǎn)可區(qū)別全染色；鄰點(diǎn)可區(qū)別全色數(shù)； k4-minor-free圖

本文所考慮的圖均為連通、有限、無(wú)向的簡(jiǎn)單圖. V（ G）和 E（ G）分別表示圖G的頂點(diǎn)集和邊集，δ（ G）和Δ （G）分別表示G中頂點(diǎn)的最小度和最大度.設(shè)u ∈ V，在圖G中與u相鄰的點(diǎn)的全體的個(gè)數(shù)稱為u的度數(shù)，記為 d（ u）.把 d（ u ）= k的點(diǎn)叫做k-點(diǎn)，類似地，把 d（ u ）＞ k的點(diǎn)叫做k+-點(diǎn)，d （ u ）＜k的點(diǎn)叫做k--點(diǎn)，度為1的點(diǎn)被稱為葉子.如果一個(gè)圖H能從另一個(gè)圖G的子圖通過(guò)一些列的邊收縮而得到，則稱H是G的一個(gè)minor（圖子式）；如果H不是G的圖子式則稱G是H-minor-free的.

定義[1]574對(duì)階數(shù)不小于2的連通圖 G（ V, E），令f為 V（ G ）∪E（ G ）→｛1, 2,… ,k ｝的映射，其中k為正整數(shù)，對(duì)任意的 u∈ V（ G），記 C（ u ）= ｛f （ u ）｝∪ ｛f（ uv） uv ∈E（ G）｝，如果 f滿足下列條件：

1）對(duì)任意的 uv, vw ∈ E（ G），u ≠ w，有 f（ uv ）≠ f（ vw）；

2）對(duì)任意的 uv∈ E（ G），若 f（ u ）≠ f（ v）、 f（ u ）≠ f（ uv）、 f（ v） ≠ f（ uv），則f為圖G的一個(gè)k-正常全染色，最小的k值為圖G的全色數(shù)，記為 χt（G）.進(jìn)一步，如果f還滿足：

3）對(duì)任意 uv ∈ E（ G），u ≠ v，有 C（ u ）≠ C（ v），則稱f為圖G的一個(gè)k-鄰點(diǎn)可區(qū)別全染色，簡(jiǎn)記為k-AVDTC，且稱 χat（G ）= min ｛k G的 k -AVDTC｝為圖G的鄰點(diǎn)可區(qū)別全色數(shù).

Behzad[2]和Vizing[3]分別獨(dú)立地提出了有關(guān)圖的全染色猜想.

猜想1 對(duì)任意的簡(jiǎn)單圖G， χt（G ）≤ Δ （G）+2.

2004年張忠輔等[1]首次提出了鄰點(diǎn)可區(qū)別全染色的概念，證明了完全圖、完全二部圖、圈、扇、輪和樹(shù)等簡(jiǎn)單圖的鄰點(diǎn)可區(qū)別全色數(shù)，并根據(jù)這些結(jié)論，對(duì)照全染色猜想提出了猜想2.

猜想2 對(duì)階數(shù)不小于2的簡(jiǎn)單連通圖G，有 χat（G ）≤ Δ （G）+3.

文獻(xiàn)[4-5]分別獨(dú)立證明了對(duì)于 Δ （G）= 3的圖猜想2成立.

引理1[1]575若G是一個(gè)圖，則 χat（G）≥ Δ+1；當(dāng)G有兩個(gè)相鄰的最大度點(diǎn)時(shí)，χat（G ）≥ Δ+2.

引理2[4-5]若 Δ （G）= 3，則 χat（G）≤6.

文獻(xiàn)[6-9]研究了2-連通外平面圖的鄰點(diǎn)可區(qū)別全色數(shù)，文獻(xiàn)[10]證明了外平面圖中猜想2成立.本文主要討論 k4-minor-free圖的鄰點(diǎn)可區(qū)別全染色，并證明：若G是一個(gè) Δ （G）≥ 5的 k4-minor-free圖，則Δ （G ）+ 1≤ χat（G）≤Δ （G）+2，且 χat（G ）=Δ （G）+ 2當(dāng)且僅當(dāng)G包含相鄰的最大度點(diǎn).

圖G是外平面的當(dāng)且僅當(dāng)G是 k4-minor-free和 k2,3-minor-free的，因此 k4-minor-free圖是包含外平面圖在內(nèi)的一類特殊平面圖.本文的主要定理推廣了文獻(xiàn)[10]中的結(jié)論.

引理3[11]每一個(gè) Δ （G）≥ 3的連通 k4-minor-free圖G必含有 C1到 C5這5個(gè)子圖之一.

415

C1：一個(gè)頂點(diǎn)v相鄰于至少一個(gè)葉子和至多兩個(gè)3+-點(diǎn).

C2：一條路x1x2…xm,m ≥4，滿足 d（ x1）≥ 3， d（ xm）≥ 2， d（ xi）=2,i = 2,3,… ,m -1.

C3：一個(gè)3-圈xyzx使得 d（ x）=2， 2≤ d（ y）≤3， d（ z）≥ 3.

C4：兩個(gè)3-圈 xx1zx和 yy1zy使得 d（ z）= 4， d（ x1）= d（ y1）= 2.

C5：一個(gè)4-圈 y1y2y3y4y1使得 d（ y2）= d（ y4）= 2， d （y1）,d （y3）≥ 3，并且 y1至多與兩個(gè)3+-點(diǎn)相鄰.

2 主要結(jié)果

定理1 若G是一個(gè) Δ （G）≥ 4的 k4-minor-free圖，則 χat（G ）≤ Δ （G）+2.

1） C1：存在一個(gè)k-點(diǎn)v相鄰于 v1, v2,… ,vk，使得 d（ v1）=1， d（ vi）≤ 2（ i=2,3,… ,k -2）.

令H = G - v1，由歸納假設(shè)，H有一個(gè)應(yīng)用顏色集合 C= ｛1,2,…,Δ （G）+2｝的 （Δ （ G）+ 2）-鄰點(diǎn)可區(qū)別全染色f.不失一般性，假設(shè) f（ v）=1， f（ vvi）=i（ i= 2,3,… ,k ）.顯然 Δ （G ）≥ d（ v ）=k.證明又分以下3種子情況：

① k=2.若 d（ v2）≠ 2，用3染 vv1.若 d（ v2）= 2，如果存在 c∈ ｛3, 4,5｝使得 c ? Cf（v2），給 vv1染c，給v1染集合 C ｛f（ v ）,f（ vv1）｝中的顏色.

2） C2：存在一條路 x1x2…xm,m ≥4，滿足 d（ x1）≥ 3， d（ xm）≥ 2， d（ xi）= 2（ i= 2,3,… ,m -1）.

令H = G - x2x3，根據(jù)歸納假設(shè)，圖H有一個(gè)應(yīng)用顏色集合 C= ｛1,2,…,Δ （G）+2｝的 （Δ （ G）+2）-鄰點(diǎn)可區(qū)別全染色f.若 d（ x4）≠2，給 x2染或改染顏色 a ∈C ｛f（x1x2）,f（x3x4）,f（ x1）,f（ x3）,｝且在集合C ｛f（ x3）,f（ x1x2）,f（ x3x4）,a｝ 中任選一種顏色給 x2x3.若 d（ x4）= 2，給 x3x4染或改染顏色a ∈ C｛f （ x2）， f（ x4）， f（ x5）,f（ x4x5）｝，給 x3染或改染 b ∈C ｛a, f（ x2）, f（ x4）,f（ x4x5）｝且在集合C ｛a, b, f（ x2）,f（ x1x2）｝中任選一種顏色給 x2x3.

3） C3：一個(gè)3-圈xyzx使得 d（ x）=2， 2≤ d（ y）≤3.

令H = G - xy，由歸納假設(shè)，H有一個(gè)應(yīng)用顏色集合 C= ｛1,2,…,Δ （G）+2｝的 （Δ （ G）+ 2）-鄰點(diǎn)可區(qū)別全染色 f.證明又分為以下3種子情況：

① d（ y）=2.給xy染色集合 C ｛f（ x ）,f（y ）,f（ xz） ,f（yz ）｝中的顏色，給x染或改染集合C ｛f（y ）,f（ z） ,f（ xy ）,f（ xz） ｝中的顏色.

② d（ y）= 3.令u ≠ x，z是y的第3個(gè)鄰點(diǎn). 1a d（ z）≥ 4.i）若 d（ u）≠3，給xy染集合 C ｛f（x） ,f（y ）,f（xz） ,f（yz） ,f（yu ）｝中的顏色.ii）若d（ u）= 3，令u1, u2≠ y是u的另兩個(gè)鄰點(diǎn).若給xy正常染色即可.否則，給y改染一個(gè)顏色 a∈C （Cf（u ）∪ ｛f （ z ）｝），然后對(duì)xy正常染色即可.因?yàn)?/p>

4） C4：存在兩個(gè)3-圈 xx1zx和 yy1zy使得 d（ z）=4， d（ x1）= d（ y1）= 2.

根據(jù)情況3），可以假設(shè) d（ x）≥ 4、 d（ y）≥4，令 H = G - zx1，由歸納假設(shè)，H有一個(gè)應(yīng)用顏色集合C= ｛1,2,…,Δ （G）+2｝的 （Δ （ G）+ 2）-鄰點(diǎn)可區(qū)別全染色f，證明又分為以下2種子情況：

① d（ x）,d（ y）≥5.給 zx1染集合 C ｛f（ xz） ,f（yz） ,f（ xx1）,f（ zy1）,f（ x1）,f（ z） ｝中的顏色.

② 假設(shè) d（ x）= 4，令 u1, u2≠ x1，z是x的另外兩個(gè)鄰點(diǎn)，不妨設(shè) f（ x）=1、 f（ xu1）= 2、 f（ xu2）= 3、f（ xz）=4、 f（ xx1）= 5,6 ? Cf（x ）.若d（ y）≥5，如果 6 ?｛f（ z） ,f（ zy ）,f（ zy1）｝，給 zx1染6，給 x1染或改染集合 C ｛f（ x ）,f（ z） , f（ xx1）,f（ x1z ）｝中的顏色.否則，給 zx1正常染色即可.若 d（ y）= 4，因?yàn)镃f（y）=5且C≥6，存在一個(gè)顏色 a ∈C Cf（y ），當(dāng) a≥ 6，若 a ? Cf（z），給 zx1染a， x1染或改染C ｛ f（ xx1）,f（ zx1）,f（ x ）,f（ z） ｝中的顏色，否則，給 zx1正常染色；當(dāng)1 ≤ a≤ 5，i）a ∈ Cf（z），若 6 ? Cf（z），給 zx1染6，x1染或改染 C ｛f（ xx1）,f（ zx1）,f（ x）,f（ z） ｝中的顏色，若 6 ∈ Cf（z），只需對(duì) zx1正常染色.ii）a? Cf（z），給y1z改染顏色a，y1染或改染集合 C ｛f（y ）,f（ z） , f（yy1）,f（y1z） ｝中的顏色，隨后證明與前面情況相同.

5） C5：一個(gè)4-圈 y1y2y3y4y1使得 d（y2）= d（y4）= 2，d（ y1）,d（ y3）≥ 3，并且 y1至多與兩個(gè)3+-點(diǎn)相鄰.

令 u1, u2,… ,um是 y1不同于 y2和 y4的鄰點(diǎn)，如果 m≥ 3，進(jìn)一步假設(shè)對(duì)于任意 i= 1,2,… ,m -2有d（ ui）≤2.不失一般性，假設(shè) d（ y1）= d（ um-1）= d（ um），否則結(jié)論很容易證出.令 H = G - y1y2，根據(jù)歸納假設(shè)，H有一個(gè)應(yīng)用顏色集合 C= ｛1,2,…,Δ （G）+2｝的 （Δ （ G）+ 2）-鄰點(diǎn)可區(qū)別全染色f.不失一般性，假設(shè) f（y1）=1、f（y1y4）= 2、 f（y1ui）= i+2（ i= 1,2,… ,m ）.因C =Δ （G）+2，d（ y1）=m+2≤Δ （G），可以看出 m+ 3,m +4∈C .

① 若 存 在 c∈｛m +3,m +4｝使 得 c∈ Cf（um-1）∩ Cf（um）， 給y1y2染 a∈｛m +3,m + 4｝｛c｝.當(dāng)f（y2y3）= a時(shí)，需交換 y2y3和 y3y4的顏色，因?yàn)?f（y2y3）≠ f（y3y4）和 a≠ 1,2，給 y2染或改染集合C ｛ f（y2y3）, f（y3y4）, f（y3）,1,a｝中的顏色；當(dāng) f（y2）= a時(shí)，給 y2染或改染集合 C ｛1,a，f（y2y3）,f（y3）｝中的顏色.

② 若 ｛m +3,m +4｝ ? Cf（um-1）Cf（um）或 ｛m + 3,m +4｝ ∈ Cf（um）Cf（um-1）， 給y1y2染 集 合｛m + 3,m + 4｝f（y2y3）中的顏色，給y2染或改染 C ｛1,a, f（y2y3）,f（y3）｝中的顏色.

③ 若存在 c∈｛m +3,m +4｝使得 c? Cf（um-1）∪ Cf（um），給y1y2染c，當(dāng) f（y2y3）= c或 f（y2）= c時(shí)，證明與①相同.

④ 假設(shè) m +3∈ Cf（um-1）Cf（um）和 m +4∈ Cf（um）Cf（um-1），給y1y4染 a∈｛m +3,m + 4｝｛f（y3y4）｝，給y1y2染 b∈ ｛m + 3,m + 4｝｛a｝，給y2染或改染集合 C ｛1,b, f（y2y3）,f（y3）｝中的顏色，給 y4染或改染集合C ｛1,a, f（y3y4）,f（y3）｝中的顏色.

定理2 若G是一個(gè) Δ （G）≥ 5且沒(méi)有相鄰最大度點(diǎn)的 k4-minor-free圖，則 χat（G ）≤ Δ （G）+1.

若G含有 C1.令 H = G - v1，H有一個(gè)應(yīng)用顏色集合 C= ｛1,2,…,Δ （G）+1｝的 （Δ （ G）+ 1）-鄰點(diǎn)可區(qū)別全染色f.如果 k = d（ v ）＜Δ （G），那么C=Δ （G）+1 ≥ k+ 2，證明類似于定理1中的 C1.如果k = d（ v ）=Δ （G），那么 d（ vi）＜ Δ （G）（ i = k - 1,k），根據(jù)假設(shè)，只需對(duì) vv1正常染色，給 v1染集合C ｛f（ v ）,f（ vv1）｝中的顏色.

由定理1和定理2，立即推出下面的結(jié)論：

定理3 若G是一個(gè) Δ （G）≥ 5的k4-minor-free圖，則 Δ （G）+ 1≤ χat（G）≤ Δ （G ）+2，且 χat（G）= Δ （G）+ 2當(dāng)且僅當(dāng)G包含相鄰的最大度點(diǎn).

[1]張忠輔，陳祥恩，李敬文，等.關(guān)于圖的鄰點(diǎn)可區(qū)別全染色[J].中國(guó)科學(xué)：A輯，2004,34(5):514-583.

[2]BEHZAD M.Graphs and their chromatic numbers[D].New York:Michigan State University,1965.

[3]VIZING V G.Some unsolved problems in graph theory[J].Uspekhi Mat Nauk,1968,23:117-134.

[4]CHEN Xiangen.On the adjacent vertex distinguishing total coloring numbers of graphs with Δ=3[J].Discrete Math,2008,308(17):4003-4007.

[5]WANG Haiying.On the adjacent vertex distinguishing total chromatic number of the graph with Δ(G)=3[J].J Comb Optim,2007,14:87-109.

[6]張少君，陳祥恩，劉信生.關(guān)于Δ(G)=5的2-連通外平面圖的鄰點(diǎn)可區(qū)別全色數(shù)[J].西北師范大學(xué)：自然科學(xué)版，2005,41(5):8-18.

[7]安明強(qiáng).關(guān)于 （）6GΔ = 的2-連通外平面圖的鄰點(diǎn)可區(qū)別全色數(shù)[J].河西學(xué)院學(xué)報(bào)，2005,21(5):25-29.

[8]CHEN Xiangen,ZHANG Zhongfu.Adjacent-vertex-distinguishing total chromatic number on 2-connected outerplane graph with Δ(G)≤4[J].Journal of Lanzhou University:Natural Science,2006,42(6):96-102.

[9]朱俊俏，卜月華.2-連通外平面圖的鄰點(diǎn)可區(qū)別全染色[J].浙江師范大學(xué)學(xué)報(bào)，2009,32(1):33-39.

[10]WANG Yiqiao,WANG Weifan.Adjacent vertex distinguishing total colorings of outerplanar graphs[J].J Comb Optim,2010,19:123-133.

[11]WANG Yiqiao,WANG Weifan.Adjacent vertex distinguishing edge colorings of4k -minor-free graphs[J]. Applied Math Letters,2011,24:2034-2037.

Adjacent Vertex Distinguishing Total Coloring of4k-minor-free Graphs

SHI Xiao-yi,ZHANG Ning,WAN Hui-min
(College of Science,China University of Mining&Technology,Xuzhou 221008,China)

A proper total coloring of graphG is called adjacent vertex distinguishing if the color sets of every two adjacent vertices are different.The paper determines the adjacent vertex distinguishing total chromatic numbers of4k-minor-free graphs.

total coloring;adjacent vertex distinguishing total coloring;adjacent vertex distinguishing total chromatic number;4k-minor-free graphs

1006-7302（2012）04-0009-05

O157.5

A

2012-03-29

中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)基金資助項(xiàng)目（2010LKSX06）

史小藝（1986—），女，江蘇沛縣人，在讀碩士生，研究方向?yàn)閳D論及其應(yīng)用.

熊玉濤]