關于廣義θ—圖的鄰點可區別染色的簡單證明

王志丹+王治文

摘 要 在《經濟數學》等雜志上已經用窮染法給出了廣義θ-圖的鄰點可區別全染色和鄰點可區別邊染色， 但方法太過繁瑣. 本文結合P.N. Balister方法從結構上更為簡潔的證明廣義θ-圖的鄰點可區別染色的相關猜想.

關鍵詞 圖， θ-圖； 鄰點可區別全染色；鄰點可區別邊染色

中圖分類號 O157.5 文獻標識碼 A

Abstract In the Journal of Quantitative Economics and so on， the general method is used to give the adjacent vertex distinguishing total coloring and the adjacent vertex distinguishing edge coloring of the general θ-graph. But the methods are too complicated. In this paper， P.N.Balister method is used to prove the relative conjectures of the adjacent vertex distinguishing coloring of the general θ-graph.

Key words graph， θ-graph， adjacent vertex distinguishing total-coloring，adjacent vertex distinguishing edge-coloring

參考文獻

[1] 張和平，歐陽克智. θ-圖及其線圖的聯結數[J].蘭州大學學報（自科版），1992，28（3）：6-11.

[2] 張忠輔，陳祥恩，李敬文，等.關于圖的鄰點可區別全染色[J].中國科學A，2004， 34（5）：574-583.

[3] ZHANG Z F，LIU L Z， WANG J F. Adjacent strong edge coloring of graphs[J].Applied Mathematics Letters，2002，15（5）：623-626.

[4] 閆麗宏，王治文，張忠輔.廣義θ-圖的鄰點可區別的全染色（英文）[J].經濟數學， 2007，24（1）：103-106.

[5] BALISTER P N， GYORI E， LEHEL J，et al.Adjacent vertex distinguishing edge-colorings[J]. Siam Journal on Discrete Mathematics，2007，21（1）：237-250.

[6] BONDY J A，MURTY U S R.Graph theory with applications[M].New York： The Macmillan Press Ltd，1976.endprint