圖Ｐ_ｕ，ｖ（ｎ）的鄰強邊染色

摘要：u，v兩點間連接n條內部不相交的路，其中最多有一條長度為1，記做P P_u，v (n)。給出一個算法，利用計算機尋找邊染色的規律，進一步給出了P P_u，v (n)的鄰強邊染色法，從而確定了P P_u，v (n)的鄰強邊染色數。進一步討論了至多含有兩個頂點度大于2的部分簡單連通圖的鄰強邊色數。

關鍵詞：鄰強邊色數； k－邊可著色；頂點度

中圖分類號：TP301文獻標志碼：A

文章編號：1001－3695(2008)06－1685－02

0引言

圖的染色問題是圖論中主要研究課題之一。圖的染色包括點、邊等不同種類的染色。其中，圖的鄰強邊染色在許多領域有很重要的應用。許多圖論工作者在這方面也做了大量的工作。H·Hatami在文獻[1]中用概率方法給出了最大度Δ≥1020的無孤立邊的圖的鄰強邊色數的上界。文獻[2~4]也分別對一些圖的幾種特殊的染色數進行了研究。張忠輔等人在文獻[5，6]中對圖的鄰點可區別全染色、鄰強邊染色進行了研究，得到了圈、完全二部圖、完全圖的鄰點可區別全色數和鄰強邊色數，并提出了猜想。他們在文獻[7]中給出了兩頂點間有三條內部不交路的θ－圖的鄰強邊色數。本文在此基礎上利用一種算法，尋找鄰強邊染色規律，確定了圖Pu，v(n) 的鄰強邊色數，并進一步討論了至多含有兩個頂點度大于2的部分簡單連通圖的鄰強邊色數的情況，從而證明了此類圖也滿足文獻[6]的猜想。



上述文中的三個定理表明這些圖的鄰強邊色數滿足文獻[6]中的猜想。

參考文獻：

[1]HATAMI H．Δ+300 is a bound on the adjacent vertex distinguishing edge chromatic number[J]．Journal of Combinatorial Theory:Series B，2005，95 (2): 246－256.

[2]AKBARI S， BIDKHORI H，NOSRATI N．R－strong edge colorings of graphs[J]．Discrete Mathematics，2006，306 (23): 3005－3010.

[3]ZHANG Zhong－fu，LI Jiang－wen，CHEN Xiang－en，et al. D(β)－vertex－distinguishing total coloring of graphs[J]．Scince in China Series A:Mathematics，2006，49(10):1430－1440.

[4]EDWARDS K，HORNAK M，WOZNIAK M．On the neighbour－distinguishing index of a graph[J]．Graphs and Combinatorics，2006，22 (3): 341－350.

［5］ZHANG Zhong－ fu，CHEN Xiang－en，LI Jing－wen，et al. On adjacent－vertex－distinguishing total coloring of graphs[J]．Science in China Series A:Mathematics，2005，48 (3):289－299.

[6]ZHANG Zhong－fu，LIU Lin－zhong，WANG Jian－fang．Adjacent strong edge coloring of graphs[J]．Applied Mathematics Letters，2002，15 (5): 623－626.

[7]王文杰，張忠輔．θ－圖的鄰強邊染色[J]．新疆大學學報：自然科學版，2004，21（3）：237－239.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文