超圖圈偶邊著色

朱俊杰

(昌吉學院數學系 新疆 昌吉 831100)

超圖圈偶邊著色

朱俊杰

(昌吉學院數學系 新疆 昌吉 831100)

本文根據N.Alon給出的一定范圍內的圈偶邊著色定義及色數定義，將其向超圖上推廣，得到了超圖的最大偶邊著色數。

圈偶邊著色;超圖

1 基本概念

1983年B.Devadas Acharya在［1］中首先提出了圖圈偶邊著色的概念，這一概念來源于對平衡標號圖的研究，B.Devadas Acharya同時給出了圖最大圈偶邊著色的色數，一年后N.Alon給出了一定范圍內最小圈偶邊著色的等價定義及色數，本部分將圖圈偶邊著色的的概念推廣到超圖中，并得出了超圖最大圈偶邊著色的若干性質。

定義1［2］令X=(x1，x2，…，xn)是一個有限集，關于X上的一個超圖H=(E1，E2，…，En)是X上一個有限子集簇，使得①Ei≠φ(i=1，2，…，m);②∪mi=1Ei=X。一個超圖H=(E1，E2，…，En)若還滿足③Ei=Ej?i=j則稱H為簡單超圖。

定義2［3］超圖的圈偶邊著色，設H=(V，E)是一個頂點數為n分支數為k的有限無環的無向超圖，設P={Ei}是E(H)的一個劃分，使其滿足:對于H中的每一個圈Z，至少存在一個Ei∈P使得

定義3［2］設v是超圖H中一個頂點，v被稱為H的一個割點如果H－v的連通分支數增加。H的所有部分超圖中，不存在割點的部分超圖稱為H的塊。

由定義可知，H中圈的集合是它中塊的圈集合之并。于是有下列性質:

性質1 H是超圖，εmin(H)=maxB∈ΒHεmin(B)，其中ΒH是H中塊的集合。

性質2 H是超圖，εmax(H)，其中ΒH是H中塊的集合。

2 主要結果及證明

首先，我們給出France Dacar在1998年證明的結論。然后應用該結論分別推導出連通簡單超圖及多個連通分支簡單超圖最大圈偶邊著色數的上界為和。最后在此基礎上得到一致連通無圈和單圈超圖最大圈偶著色的色數為別為和。

引理1［4］設H是n個頂點p個連通分支的超圖，邊集為{E1，E2，…，Em}，則H不包含圈當且僅當

由定理1可得如下兩個推論。

推論1如果H是n個頂點k個連通分支的簡單r－一致超圖，那么

在圖中有結論:任何n個頂點k個連通分支的圖G，εmax(H)=n－k。那么我們自然猜想在r－一致超圖H上是否有εmax(H)

定理2 H是n個頂點k個連通分支邊集為(E1，E2，…，Em)的r－一致超圖。若H不包含圈，則

證:若H不包含圈，則顯然有εmax(H)=m。又因為H是r－一致超圖，由引理m(r－1)=n－k，所以

定理3 H是n個頂點r－一致的連通超圖。若H只包含一個圈，則

證:H包含一個圈不妨設為(x1，E1，x2，E2···，xp，Ep)，現去掉圈上的一條邊E1，形成超圖H'，即H'是(Ej|j∈{2，3，4，···，p})對H誘導的部分超圖。H'仍是r－一致超圖且不包含圈。設H'的頂點數是n'，連通分支數是t，則n'=n－s(s是E1中一度點的個數)。由定理2因為E1中除x1，x2以外的非一度點最多包含在H'的一個連通分支中，且E1中的x1，x2一定包含在H'的一個連通分支中，所以t≤r－s－1。又因為E1中除x1，x2的任一非一度點x必包含在H'的一個連通分支中且這個連通分支不包含E1中的其他點，否則假設一個連通分支P∈H'還包含E1的另一個點，則在P中存在一條x到的鏈(x，E1'，···，Eq')，這條鏈與E1在H中形成一個圈，與H只包含一個圈矛盾!所以t=r－s－1即t+s=r－1。因此。由于H'不包含圈，則顯然有εmax(H')=m(H')(這里用m(H')表示H'的邊數)，那么－1=m(H')，而m(H)=m(H')+1=

3.結束語

本文最終得到了一致的連通無圈和單圈超圖最大圈偶著色的準確色數，應用同樣方法也能對最小圈偶著色的色數進行估計，這樣做使超圖的圈結構更加清楚，同時也提供了研究超圖圈的一種方法。當然，以上結論并沒有得到一般超圖圈偶著色的準確色數，這將有待進一步研究。

［1］B.Devadas Acharya.Even Edge Colorings of a Graph［J］.Journal of Combi－natorial Theory，series B 35(1983)78－79.

［2］C.Berge.Hypergraphs:Combinatorics of Finite Sets［M］.North Holland:Amst－erdam，1973.

［3］N.Alon.Even Edge Colorings of a Graph［J］.Journal of Combinatorial Theory，series B 38(1985)93－94.

［4］France Dacar.The cyclicity of a hypergraph［J］.Discrete Mathematics，182(1998)，53－67.

［5］Sundar Vishwanathan.On 2－coloring k－uniform hypergraphs［J］.Journal of Combinatorial Theory，series A 101 (2003)168－172.

O186

A

1671－6469(2011)05－0094－03

2011－09－12

昌吉學院研究生科研啟動基金(2010SSQD022)

朱俊杰(1982－)，男，新疆阿克蘇人，昌吉學院數學系，講師，研究方向:離散數學。

(責任編輯:馬海燕)