輪形圖的全著色

楊鵬輝

(安徽財經(jīng)大學(xué)統(tǒng)計與應(yīng)用數(shù)學(xué)學(xué)院，安徽蚌埠 233030)

輪形圖的全著色

楊鵬輝

(安徽財經(jīng)大學(xué)統(tǒng)計與應(yīng)用數(shù)學(xué)學(xué)院，安徽蚌埠 233030)

輪形圖;全著色;弱全色數(shù);強全色數(shù)

圖的著色理論起源于1852 年 Francis Guthris提出的“四色猜想”［1］，自1965 年 Vzing［2］和 Behzad M［3］分別提出圖的全著色概念后，全著色理論就在圖著色理論中占有很重要的地位.1966年Behzad M首次提出超圖，逐漸地著色理論被引入到超圖中來.隨著超圖理論的不斷完善，超圖的全著色也逐漸被學(xué)者們所重視，現(xiàn)在超圖的全著色更是學(xué)者們所熱衷的研究對象.對于一般圖中輪形圖和扇形圖的全著色，文獻(xiàn)［4－5］中已經(jīng)有了很好的結(jié)論.

1 基本概念

定義1［6］超圖H的弱全著色(Weak Total Coloring)是映射

定義4頂點v的輪W(v)定義為S(v)□Cn，形如K1×Cn－1，其中S(v)是以點v為中心的超星(見圖1)，Cn是超圖中長度為n的線性超圈，星與圈的交點恰是圈中邊與邊的交點，中心v稱為輪心，超星的邊稱為輪輻，圈的邊稱為輪邊，如圖2所示.

圖1 超星

圖2 輪形圖

通過輪的定義可知，d(v)=Δ=E(S(v))=n，則輪共有2Δ=2n條超邊，其中Δ條輪輻，Δ條輪邊，還有Δ個3度點.文中用Δ表示超圖中的最大度，其他的相關(guān)概念在文獻(xiàn)［5－6］中均可以找到.

2結(jié)論

引理 1［9］設(shè)S(v) 是星，其邊集合E(S(v))={E1，E2，…，EΔ} 則

2)證明輪的強全色數(shù)是M+1.

M+1種顏色用集合C={1，…，M+1}表示，定義映射φ∶V(H)∪E(H)→C如下

若減少一種顏色，使用M種顏色著色，當(dāng)M=Δ時，根據(jù)強全著色定義可知，中心點v與Δ條超邊就需要Δ+1種不同的顏色，則M=Δ種顏色不滿足;當(dāng)存在p{1，2，…，Δ}s.t.M=rp時，按照強全著色定義，超邊Ep需要rp+1種不同的顏色，M=rp種顏色不滿足.因此，(S(v))＞M.

［1］ORE O.The Four-Color Problem［M］.New York:Academic Press，1976.

［2］VIZING V G.Some unsolved problems in graph theory［J］.Uspekhi Mat.Nauk，1968，23(6):117 –134.

［3］BEHZAD M.Graphs and their chromatic［D］.Michigan State University，1965.

［4］黃斌，張先迪.一些圖的全著色計數(shù)［J］.四川師范大學(xué)學(xué)報:自然科學(xué)版，1998，21(5):523－526.

［5］張忠輔，陳祥恩，李敬文，等.關(guān)于圖的鄰點可區(qū)別全染色［J］.中國科學(xué)A輯，2004，34(5):574－583.

［6］WANG Wei-fan，ZHANG Ke-min.Coloring of Hypergraphs［J］.Advances in Mathematics，2000，29(2):115 －136.

［7］HARARY F.Graph Theory［M］.London:Addison-Wesley Publishing Company，1969.

［8］貝爾熱 C.超圖-有限集合的組合學(xué)［M］.卜月華，張克民，譯.南京:東南大學(xué)出版社，2002.

［9］楊鵬輝.星的全著色和計數(shù)［J］.重慶大學(xué)學(xué)報:自然科學(xué)版，2007，30(5):119－122.

Total Coloring of Wheels

YANG Peng-hui

(Department of Statistic and Applied Mathematics，Anhui University of Finance and Economics，Bengbu 233030，China)

The total chromatic number χT(H)of hypergraphHis the minimum number of colors needed to color the vertices and edges ofHso that the incident or adjacent elements have distinct colors.The total coloring of hypergraph contains weak total coloring and strong total coloring.In the paper，the characteristics of the total colorings of wheelW(v)were discussed ，and the chromatic numbers of them，(W(v))=Δ+1，(W(v))=M+1 were obtained.

wheels;total coloring;weak total chromatic number;strong total chromatic number

O 157.5 < class="emphasis_bold">文獻(xiàn)標(biāo)志碼:A

A

1004－1729(2011)01－0008－03

2011－01－21

楊鵬輝(1981－)，女，安徽淮南人，安徽財經(jīng)大學(xué)統(tǒng)計與應(yīng)用數(shù)學(xué)學(xué)院講師，碩士.