徐 聞, 陳 敏

(浙江師范大學(xué) 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院, 浙江金華321004)

§1 引 言

本文所研究的圖均為有限無向簡單圖, 未定義的符號請參見文獻(xiàn)[1]. 如果能將G畫在平面上, 使得它的邊僅在端點(diǎn)處相交, 則稱G為可平面圖. 一個平面圖是指一個可平面圖的平面嵌入.令V(G),E(G),F(G),?(G)分別表示平面圖G的點(diǎn)集, 邊集, 面集以及最大度. 在平面上嵌入一棵樹T, 使得T沒有度為2的點(diǎn), 且至少有一個度數(shù)不小于3 的頂點(diǎn). 用圈C連接T的所有葉子點(diǎn),這樣得到的一個平面圖叫做哈林圖(Halin graph). 通常記為G=T ∪C, 其中T稱為G的特征樹.輪圖是特殊的哈林圖, 通常用Wn=K1+Cn?1表示n階輪圖, 其中Cn?1為n ?1個頂點(diǎn)的圈.

平面圖的點(diǎn)邊染色(或稱全染色)問題最早由Behzad[2]和Vizing[3]獨(dú)立研究. 令G是一個圖.圖G是點(diǎn)邊k-可染的是指存在映射π:V(G)∪E(G)→{1,··· ,k}, 使得任意兩個相鄰的頂點(diǎn),任意兩條相鄰的邊, 以及任意兩個相關(guān)聯(lián)的頂點(diǎn)和邊都染不同的顏色. 圖G的點(diǎn)邊色數(shù), 記為χve(G), 定義為使得G是點(diǎn)邊k-可染的最小正整數(shù)k的值.

Behzad[2]猜想:每個簡單圖G都是點(diǎn)邊(?(G)+2)-可染的. Rosenfeld[4]和Vijayaditya[5]均證明了當(dāng)?(G) = 3時猜想成立. Kostochka[6]驗(yàn)證了?(G)∈{4,5}的情形. 而Sanders和Zhao[7]證明了滿足?(G)≥7的平面圖G是點(diǎn)邊(?(G)+2)-可染的. 進(jìn)一步, Borodin[8]證明了?(G)≥9的平面圖G是點(diǎn)邊(?(G)+1)-可染的. 對于平面圖的點(diǎn)邊染色問題, ?(G) = 6的情形至今仍未能完全解決.

近年來, 在點(diǎn)邊染色的基礎(chǔ)上, Fabrici, Jendrol’和Voigt[9]提出了一個新的染色概念, 即: 平面圖的弱點(diǎn)邊染色. 對于任意的兩條相鄰邊e1和e2, 若它們關(guān)聯(lián)同一個面且在該面的邊界上連續(xù)出現(xiàn), 則稱e1和e2是面相鄰的. 平面圖G是弱點(diǎn)邊k-可染的是指存在映射π:V(G)∪E(G)→{1,··· ,k}, 使得任意兩個相鄰的頂點(diǎn), 任意兩條面相鄰的邊, 以及任意兩個相關(guān)聯(lián)的頂點(diǎn)和邊都染不同的顏色. 若平面圖G有弱點(diǎn)邊k-染色, 則稱G是弱點(diǎn)邊k-可染的. 平面圖G的弱點(diǎn)邊色數(shù)是指使得G是點(diǎn)邊k-可染的最小正整數(shù)k的值, 用ˉχve(G)表示. 顯然, ˉχve(G)≤χve(G). 在文獻(xiàn)[10]中, Fabrici, Jendrol’和Vrbjarov′a證明了每個無環(huán)且無割邊的連通平面圖是弱點(diǎn)邊6-可染的. 此外, 極大平面圖和外平面圖也均由Fabrici, Jendrol’和Voigt[10]證明是弱點(diǎn)邊5-可染的.

本文旨在找出其他滿足弱點(diǎn)邊5-可染的平面圖類, 得到以下結(jié)論.

定理1 哈林圖是弱點(diǎn)邊5-可染的.

需指出存在輪圖W4的弱點(diǎn)邊色數(shù)恰好為5, 詳見引理1. 由此可見定理1的上界5是可達(dá)的.

§2 引理與記號

令G是哈林圖. 設(shè)v ∈V(G), 用dG(v)表示v在G中的度數(shù), 用NG(v)表示v在G中的鄰點(diǎn)全體.稱V(C)構(gòu)成的無界面為外面,記為fo,其余面為內(nèi)面. 稱V(fo)中的頂點(diǎn)為外點(diǎn),V(G)?V(fo)中的頂點(diǎn)為內(nèi)點(diǎn). 記G的全體內(nèi)點(diǎn)的集合為Vint(G), 顯然Vint(G) =V(G)V(fo). 稱與外點(diǎn)相鄰的內(nèi)點(diǎn)為半葉子點(diǎn). 進(jìn)一步, 如果一個半葉子點(diǎn)僅和一個內(nèi)點(diǎn)相鄰, 則稱其為好半葉子點(diǎn).

引理1 對于輪圖Wn, 有ˉχve(Wn)≤5. 特別地, ˉχve(W4)=5, 而且當(dāng)n為奇數(shù)時, 有

證記輪圖Wn的內(nèi)點(diǎn)為v0, 其余外點(diǎn)按順時針方向依次為v1,v2,··· ,vn?1. 根據(jù)n的奇偶性分兩種情況討論.

情形1 當(dāng)n=2k+1, 其中k ≥2.

For small angular spread,exploiting the spatial frequency approximation model,the covariance matrix R can be approximated and expressed as

由于v1為3-點(diǎn), 易知v1v0,v1v2,v1vn?1以及v1這四個元素的顏色各不相同, 因此

§3 定理1的證明

圖1 結(jié)構(gòu)(A1)和結(jié)構(gòu)(A2)

情形1G包含結(jié)構(gòu)(A1).

令G?=G ?{v1,v2}+{xv,yv}. 顯然G?是哈林圖, 滿足?(G?)=?(G), 且

根據(jù)歸納假設(shè),G?有一個弱點(diǎn)邊5-染色π?.

不妨設(shè)π?(v) = 1,π?(vu) = 2,π?(xv) = 3, 以及π?(vy) = 4. 將xv,vy的顏色賦給G中的元素xv1和yv2. 記A={xv1,yv2}與S={v1,v2,vv1,vv2,v1v2}. 然后, 令π(s) =π?(s), 其中s ∈V(G)∪E(G)(A ∪S). 接下來說明S中的元素可以正常染好, 從而說明π?可以被延拓至G, 使得G有一個弱點(diǎn)邊5-染色π.

不難看出π(y)∈{2,3,5}. 下面按照π(y)的值分兩種子情況展開討論.

情形1.1:π(y)=3.

可給v2染顏色5, 給vv2染顏色3, 給vv1染顏色5, 給v1v2染1. 然后給v1染一種屬于

的顏色. 不難驗(yàn)證所得的染色是G的一個弱點(diǎn)邊5-染色.

情形1.2:π(y)∈{2,5}.

可給v2染顏色3,vv2染顏色5,vv1染顏色4,v1v2染顏色1. 然后給v1染一種屬于

的顏色. 容易驗(yàn)證得到的染色是G的一個弱點(diǎn)邊5-染色.

情形2G包含結(jié)構(gòu)(A2).

令G?=G ?{v1,v2,··· ,vt}+{xv,yv}. 顯然G?是哈林圖, 滿足?(G?)=?(G), 且

根據(jù)歸納假設(shè)G?有一個弱點(diǎn)邊5-染色π?. 同樣將證明π?可以被延拓至G.

首先令

其次將xv,yv在G?中的顏色分別賦予對應(yīng)于G中的元素xv1和yvt. 記A={xv1,yvt}及

然后令π(s) =π?(s), 其中s ∈V(G)∪E(G)(A ∪S). 接下來根據(jù)t的奇偶性分情況說明S中的元素也可被染好.

情形2.1:t為偶數(shù).

首先給vv1染顏色3, 給vvt染顏色2. 對于2≤i ≤t ?1, 若i為奇數(shù), 則給邊vvi?1染顏色2, 給邊vvi染顏色3, 給邊vi?1vi染顏色5, 給邊vivi+1染顏色1. 進(jìn)而給點(diǎn)vi?1染顏色3,vi染顏色2. 然后給邊v1v2染顏色1. 最后給v1染顏色α ∈{4,5}{π(x)}, 給vt染顏色β ∈{4,5}{π(y)}. 此時得到的染色是G的一個弱點(diǎn)邊5-染色.

情形2.2:t為奇數(shù).

首先給vv1染顏色3, 給vvt染顏色2. 對于2≤i ≤t ?2, 若i為奇數(shù), 則給邊vvi?1染顏色2,給邊vvi染顏色3, 給邊vi?1vi染顏色5, 給邊vivi+1染顏色1. 然后, 給點(diǎn)vi?1染顏色3,vi染顏色2,vt?1染顏色3, 給邊v1v2染顏色1. 之后, 給v1染顏色α ∈{4,5}{π(x)}, 給vt染顏色

最后給vvt?1染顏色β, 給邊vt?1vt染顏色γ ∈{4,5}{β}即可. 容易驗(yàn)證G是弱點(diǎn)邊5-可染的.

§3 結(jié)語