超圖圈偶邊著色

朱俊杰

(昌吉學(xué)院數(shù)學(xué)系 新疆 昌吉 831100)

超圖圈偶邊著色

朱俊杰

(昌吉學(xué)院數(shù)學(xué)系 新疆 昌吉 831100)

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

圈偶邊著色;超圖

1 基本概念

1983年B.Devadas Acharya在［1］中首先提出了圖圈偶邊著色的概念，這一概念來(lái)源于對(duì)平衡標(biāo)號(hào)圖的研究，B.Devadas Acharya同時(shí)給出了圖最大圈偶邊著色的色數(shù)，一年后N.Alon給出了一定范圍內(nèi)最小圈偶邊著色的等價(jià)定義及色數(shù)，本部分將圖圈偶邊著色的的概念推廣到超圖中，并得出了超圖最大圈偶邊著色的若干性質(zhì)。

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

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

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

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

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

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

2 主要結(jié)果及證明

首先，我們給出France Dacar在1998年證明的結(jié)論。然后應(yīng)用該結(jié)論分別推導(dǎo)出連通簡(jiǎn)單超圖及多個(gè)連通分支簡(jiǎn)單超圖最大圈偶邊著色數(shù)的上界為和。最后在此基礎(chǔ)上得到一致連通無(wú)圈和單圈超圖最大圈偶著色的色數(shù)為別為和。

引理1［4］設(shè)H是n個(gè)頂點(diǎn)p個(gè)連通分支的超圖，邊集為{E1，E2，…，Em}，則H不包含圈當(dāng)且僅當(dāng)

由定理1可得如下兩個(gè)推論。

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

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

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

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

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

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

3.結(jié)束語(yǔ)

本文最終得到了一致的連通無(wú)圈和單圈超圖最大圈偶著色的準(zhǔn)確色數(shù)，應(yīng)用同樣方法也能對(duì)最小圈偶著色的色數(shù)進(jìn)行估計(jì)，這樣做使超圖的圈結(jié)構(gòu)更加清楚，同時(shí)也提供了研究超圖圈的一種方法。當(dāng)然，以上結(jié)論并沒有得到一般超圖圈偶著色的準(zhǔn)確色數(shù)，這將有待進(jìn)一步研究。

［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

昌吉學(xué)院研究生科研啟動(dòng)基金(2010SSQD022)

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

(責(zé)任編輯:馬海燕)