哈林圖的弱點邊染色

徐 聞, 陳 敏

(浙江師范大學 數學與計算機科學學院, 浙江金華321004)

§1 引 言

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

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

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

近年來, 在點邊染色的基礎上, Fabrici, Jendrol’和Voigt[9]提出了一個新的染色概念, 即: 平面圖的弱點邊染色. 對于任意的兩條相鄰邊e1和e2, 若它們關聯同一個面且在該面的邊界上連續出現, 則稱e1和e2是面相鄰的. 平面圖G是弱點邊k-可染的是指存在映射π:V(G)∪E(G)→{1,··· ,k}, 使得任……