均衡完全三部圖 K3（n）的線性3－蔭度

王苒群，左連翠

（天津師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，天津 300387）

均衡完全三部圖K3（n）的線性3－蔭度

王苒群，左連翠

（天津師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，天津 300387）

考慮均衡完全三部圖K3（n）的線性3－蔭度.利用路分解的方法給出了K3（n）的線性3－蔭度la3（Κ3（n））當(dāng)n≡1，2，3（mod 4）時的比較緊的上界，利用線性k－蔭度的基本理論分別得到了它們的下界，進而得到了特殊情況下均衡完全三部圖K3（n）的線性3－蔭度的確切值.

線性k－森林；線性k－蔭度；均衡完全三部圖

本研究所涉及的圖都是簡單圖，即它們是有限的、無向的、無自環(huán)并且沒有重邊的圖.圖的一個獨立集是頂點集的一個子集合，其中的頂點是兩兩不相鄰的［1］.稱圖G是一個m－部圖，如果它的頂點集合V（G）可以劃分為m個獨立集，而這些獨立集稱為m－部圖G的分裂集.一個完全m－部圖G首先是一個m－部圖，并且邊uv∈Ε（G）的充要條件是u和v屬于不同的分裂集.當(dāng)m≥2時，將完全m－部圖記為Κn1，n2，…，nm，其中n1，n2，…，nm分別是它的分裂集的基數(shù).若n1＝n2＝…＝nm＝n，則稱此完全m－部圖為均衡完全m－部圖，記為Κm（n）.當(dāng)m＝3時，這樣的圖就稱為均衡完全3－部圖，記作Κn，n，n或Κ3（n）.

圖G的一個分解就是將這個圖分成一系列的子圖，使得圖G的每條邊恰出現(xiàn)在其中的一個子圖中.如果圖G有一個分解G1，G2，…，Gd，就稱G1，G2，…，Gd分解了圖G，或稱G能分解為G1，G2，…，Gd.

線性k－森林是每一個連通分支均為長度不超過k的路的圖.一個圖G的線性k－蔭度是將圖G的邊集合分解成的線性k－森林的最少數(shù)目，用lak（G）表示.

圖的線性k－蔭度的概念首先由Habib等［2］提出.它是邊著色的一種很自然的推廣.很顯然，一個線性1－森林是由一個匹配導(dǎo)出的，并且圖G的線性1－蔭度等于它的邊色數(shù)（或稱色指數(shù)），即la1（G）＝χ′（G）.而且，一個圖G的線性k－蔭度lak（G）也是一般線性蔭度la（G）（或者la∞（G））的一個加細(xì)，一般的線性蔭度是圖G的邊集合能分解成的線性森林（每個連通分支都是路的圖）的最少數(shù)目，此時每個分支都是沒有長度限制的路.1982年，Habib等提出了下述猜想，估計出了lak（G）的一個上界.

目前為止，已有的相關(guān)結(jié)果都是支持此猜想的，尤其是對于結(jié)構(gòu)特殊的圖，如樹［2，4，5］、立方圖［6－8］、正則圖［9－10］、可平面圖［11］、均衡完全2－部圖［12－13］和完全圖［6，12，14，15］等，此猜想都是成立的，但對于一般圖，此猜想尚未得到證明.

1 預(yù)備引理

2 主要結(jié)論

［1］ BONDY J A.Graph Theory with Applications［M］.New York：MacMillan Press，1976.

［2］ HABIB M，PEROCHE B.Lak－arboricitélinéaire des arbres［J］.Discrete Math，1983，17：307－317.

［3］ HABIB M，PEROCHE B.Some problems about linear arboricity［J］.Discrete Math，1982，41：219－220.

［4］ CHANG G J.Algorithmic aspects of lineark－arboricity［J］.Taiwanese J Math，1999，3：73－81.

［5］ CHANG G J，CHEN B L，F(xiàn)U H L，et al.Lineark－arboricities on trees［J］.Discrete Appl Math，2000，103：281－287.

［6］ BERMOND J C，F(xiàn)IUQUET J L，HABIB M，et al.On lineark－arboricity［J］.Discrete Math，1984，52：123－132.

［7］ JACKSON B，WORMALD N C.On the lineark－arboricity of cubic graphs［J］.Discrete Math，1996，162：293－297.

［8］ THOMASSEN C.Two－coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5［J］.Journal of Combinatorial Theory，1999，75：100－109.

［9］ ALDRED R E L，WORMALD N C.More on the lieark－arboricity of regular graphs［J］.Austral J Combin，1998，18：97－104.

［10］ALON N，TEAGUE V J，WORMALD N C.Linear arboricity and lineark－arboricity of regular graphs［J］.Graphs Combin，2001，17：11－16.

［11］LIH K W，TONG L D，WANG W F.The linear 2－arboricity of planar graphs［J］.Graphs Combin，2003，19：241－248.

［12］CHEN B L，HUANG K C.On the lineark－arboricity ofKnandKn，n［J］.Discrete Math，2002，254：51－61.

［13］FU H L，HUANG K C.The linear 2－arboricity of complete bipartite graphs［J］.Ars Combin，1994，38：309－318.

［14］CHEN B L，F(xiàn)U H L，HUANG K C.Decomposing graphs into forests of paths with size less than three［J］.Austral J Combin，1991，3：55－73.

［15］YEN C H，F(xiàn)U H L.Linear 2－arboricity of the complete graph［J］.Taiwanese J Math，2010，14：273－286.

［16］FU H L，HUANG K C，YEN C H.The linear 3－arboricity ofKnandKn，n［J］.Discrete Math，2008，308：3816－3823.

［17］YEN C H，F(xiàn)U H L.Linear 3－arboricity of the balanced complete multipartite graph［J］.Appl Math，2007，50：33－46.

Linear 3－arboricity of balanced complete tripartite graphΚ3（n）

WANGRan－qun，ZUOLian－cui
（College of Mathematical Science，Tianjin Normal University，Tianjin 300387，China）

The linear 3－arboricity of balanced complete tripartite graphK3（n）is studied.It is obtained that the sharp upper bounds of linear 3－arboricityla3（K3（n））whenn≡1，2，3（mod 4）by using the method of path－factorization，as well as the lower bounds by using the elementary theory of lineark－arboricity.And then the exact values of linear 3－arboricity of balanced complete tripartite graphK3（n）in some special cases are determined.

lineark－forest；lineark－arboricity；balanced complete tripartite graph

O157.5

A

1671－1114（2012）02－0010－08

2011－10－09

天津師范大學(xué)引進人才基金資助項目（5RL066）

王苒群（1987－），女，碩士研究生.

左連翠（1964－），女，教授，主要從事圖論及其應(yīng)用方面的研究.

（責(zé)任編校 馬新光）